BZOJ1007:[HNOI2008]水平可见直线(计算几何)

Description

在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为
可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.

Input

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

Output

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

Sample Input

3
-1 0
1 0
0 0

Sample Output

1 2

Solution

首先把直线按照斜率排序，再用个栈维护一下。

画个图可以发现，如果直线$i$和直线$stack[top]$的交点在直线$stack[top-1]$的左边，那么$stack[top]$就可以被弹出了。随便判判就好了。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #define N (50009)

 #define INF (1e18)

 using namespace std;

 struct Vector

 {

     double x,y;

     Vector(double xx=,double yy=)

     {

         x=xx; y=yy;

     }

 }p[N];

 typedef Vector Point;

 struct Line

 {

     double k,b;

     Point x,y;

     int id;

     bool operator < (const Line &a) const

     {

         return k==a.k?b>a.b:k>a.k;

     }

     bool operator == (const Line &a) const

     {

         return k==a.k && b==a.b;

     }

 }L[N],stack[N];

 int n,k,b,ans[N],top;

 double Cross(Vector a,Vector b) {return a.x*b.y-a.y*b.x;}

 Vector operator - (Vector a,Vector b) {return Vector(a.x-b.x,a.y-b.y);}

 inline int read()

 {

     int x=,w=; char c=getchar();

     while (!isdigit(c)) {if (c=='-') w=-; c=getchar();}

     while (isdigit(c)) x=x*+c-'', c=getchar();

     return x*w;

 }

 Point Line_Cross(Line u,Line v)

 {

     Point ans;

     ans.x=(v.b-u.b)/(u.k-v.k);

     ans.y=u.k*ans.x+u.b;

     return ans;

 }

 int main()

 {

     n=read();

     for (int i=; i<=n; ++i)

     {

         k=read(); b=read();

         L[i]=(Line){k,b};

         L[i].x=(Point){,b};

         L[i].y=(Point){,k+b};

         L[i].id=i;

     }

     sort(L+,L+n+);

     for (int i=; i<=n; ++i)

     {

         if (top && L[i].k==stack[top].k) continue;

         while (top>=)

         {

             Point p=Line_Cross(stack[top],L[i]);

             if (Cross(stack[top-].x-p,stack[top-].y-p)>) break;

             top--;

         }

         stack[++top]=L[i];

     }

     for (int i=; i<=top; ++i) ans[stack[i].id]=;

     for (int i=; i<=n; ++i) if (ans[i]) printf("%d ",i);

 }