BZOJ1007 [HNOI2008]水平可见直线 【计算几何+单调栈】
我们先按照斜率排个序,然后顺次将直线压入栈中。
设栈顶元素$top$,栈顶元素的前一个元素为$top-1$,即将压入栈的元素为$t$,那么,如果$top$与$t$的交点的横坐标比$top-1$和$top$交点的横坐标小的话,弹出栈。正确性可脑补。
# include <stdio.h> # include <algorithm> # include <string.h> using namespace std; struct lines { int A,B,C; bool operator ==(const lines &b) {return A==b.A;} }s[50010],a[50010]; int n,nn,top=1;int gg[50010]; inline int cmp(lines _a,lines _b) { return _a.A < _b.A || (_a.A == _b.A && _a.B > _b.B); } inline double g(lines x,lines y) { return (double)(y.B-x.B)/(double)(x.A-y.A); } int main() { scanf("%d",&n);nn=n; for (int i=1;i<=n;++i) { scanf("%d%d",&a[i].A,&a[i].B); a[i].C=i; } sort(a+1,a+n+1,cmp); n = unique(&a[1],&a[n+1])-&a[1]; for (int i=1;i<=n;++i) { while(top > 2 && g(s[top-1],s[top-2]) - g(s[top-1], a[i]) > -1*1e-8) top--; s[top++]=a[i]; } memset(gg,0,sizeof(gg)); for (int i=1;i<top;++i) gg[s[i].C]=1; for (int i=1;i<=nn;++i) if(gg[i]) printf("%d ",i); return 0; }