首页 > 代码库 > 【BZOJ】1007 水平可见直线
【BZOJ】1007 水平可见直线
【分析】
维护一个下凸包。
首先依照斜率来从小到大排序。
维护一个下凸包。
首先依照斜率来从小到大排序。
考虑斜率同样的,肯定仅仅能选截距大的,把截距小的给筛掉。
然后用栈来维护下凸包。先压入前两条直线。
然后对于每一条直线i,设栈中上一条直线p=stk[stk[0]]和上上条直线q=stk[stk[0]-1]。
找到i与p的交点m。p与q的交点n。
画三条直线,把n点看成固定的,因为斜率从小到大,要使得上一条直线p看不到。那么m一定在n的左边,即m.x<=n.x。
假设看不到,就退栈,直到在右边。
最后输出,注意可能会存在n=1的情况。这个么,随便处理罢...
PS:网上的代码大多数都是错的,结果还能AC,这道题的数据非常水哟。
【代码】
<span style="font-size:18px;">#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; const int N=50000; const double eps=1e-5; struct Line { double k,b; int id; }line[N],_line[N]; struct Point { double x,y; }now,last; int n,_n,stk[N]; inline int dc(double i,double j) { if (fabs(i-j)<eps) return 0; return i<j?-1:1; } int cmp(Line La,Line Lb) { int r=dc(La.k,Lb.k); return r?r<0:dc(La.b,Lb.b)>0; } inline Point get_point(int i,int j) { double k1=_line[i].k,b1=_line[i].b,k2=_line[j].k,b2=_line[j].b; Point P; P.x=(b2-b1)/(k1-k2); P.y=(b1*k2-b2*k1)/(k1-k2); return P; } inline int cmp1(int i,int j) { return _line[i].id<_line[j].id; } int main(void) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lf%lf",&line[i].k,&line[i].b),line[i].id=i; sort(line+1,line+n+1,cmp); for (int i=1;i<=n;i++) { if (_n&&!dc(line[i].k,_line[_n].k)) continue; _line[++_n]=line[i]; } stk[++stk[0]]=1,stk[++stk[0]]=2; for (int i=3;i<=_n;i++) { if (stk[0]&&!dc(_line[stk[stk[0]]].k,_line[i].k)) continue; for (;stk[0]>=2;) { last=get_point(stk[stk[0]-1],stk[stk[0]]); now=get_point(stk[stk[0]],i); if (last.x>=now.x) stk[stk[0]--]=0; else break; } stk[++stk[0]]=i; } sort(stk+1,stk+stk[0]+1,cmp1); for (int i=1;i<=stk[0];i++) { if (!line[i].id) continue; printf("%d ",_line[stk[i]].id); } printf("\n"); return 0; }</span>
【BZOJ】1007 水平可见直线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。