BZOJ 1007, 水平可见直线

2019-11-11 04:34:01

字体：大中小

来源：转载

供稿：网友

PRoblem

传送门

Mean

参见题目描述。

Analysis

将直线按斜率排序，然后从小到大依次入栈，入栈时计算该直线与栈顶元素交点。若该交点在栈顶元素与栈顶下一个元素交点的左侧（或重合），则栈顶元素被完整遮挡，出栈。反复比较，全部操作完毕后栈中元素即为可见水平直线。

Code

#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const double EPS=1e-10;const int N=50005;int n,top,s[N];bool f[N];struct Line{ int id; double a,b; bool Operator < (const Line &B) const { if(fabs(a-B.a)<EPS) return b<B.b; return a<B.a; }}l[N];double Cross(Line A,Line B){return (B.b-A.b)/(A.a-B.a);}int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf%lf",&l[i].a,&l[i].b); l[i].id=i; } sort(l,l+n); for(int i=0;i<n;i++){ while(top){ if(fabs(l[s[top]].a-l[i].a)<EPS) top--; else if(top>1 && Cross(l[s[top]],l[i])<=Cross(l[s[top-1]],l[s[top]])) top--; else break; } s[++top]=i; } for(int i=1;i<=top;i++) f[l[s[i]].id]=1; for(int i=0;i<n;i++) if(f[i]) printf("%d ",i+1); return 0;}

上一篇：正则表达式入门教程(一)

下一篇：kruskal