BZOJ1007: [HNOI2008]水平可见直线

Description

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input

Sample Output

参考了WYL8899大 的题解之后懂了

按斜率排序，用栈维护可见直线。

如右图，当前考虑直线now，栈顶top，栈顶的下一个元素top'大致的位置。

显然now和top"将把top完全遮盖。

思考一下可以得出，记两直线交点的横坐标为x(A,B)，则x(now,top)<=x(top,top')时，栈顶直线被废，弹出栈。

反复这样操作，直至不满足上面的条件，将当前直线压入栈中。

最后在栈中的直线就是答案。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; struct node{ int a,b,id; }l[60000]; bool f[60000]; int n,i,top,stack[60000]; bool cmp(node a,node b) { if (a.a == b.a) return (a.b > b.b); return (a.a < b.a); } bool check(node a,node b,node c) { double t1=(double)(b.b-a.b),t2=(double)(a.a-b.a),t3=(double)(c.b-b.b),t4=(double)(b.a-c.a); double x1=(double) t1/t2; double x2=(double) t3/t4; if (x1<=x2) return true; return false; } int main() { scanf("%d",&n); for (i=1; i<=n; i++) { scanf("%d%d",&l[i].a,&l[i].b); l[i].id=i; } sort(l+1,l+n+1,cmp); for (i=1; i<=n; i++) { if (l[i].a==l[i-1].a) continue; while (top>=2 && check(l[i],l[stack[top]],l[stack[top-1]])) top--; stack[++top]=i; } memset(f,false,sizeof(f)); for (i=1; i<=top; i++) f[l[stack[i]].id]=true; for (i=1; i<=n; i++) if (f[i]) printf("%d ",i); return 0; }