在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条直线两两不重合.求出所有可见的直线.

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

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

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const double eps=1e-6;10 const int mxn=100010;11 struct line{12     double k,b;13     int id;14 }a[mxn];15 int cmp(const line a,const line b){16     return (a.k<b.k ||(a.k==b.k && a.b<b.b ));17 }18 int n;19 int st[mxn],top=0;20 double cross(int x,int y){//交点 21     return (a[y].b-a[x].b)/(a[x].k-a[y].k);22 }23 int main(){24     int i,j;25     scanf("%d",&n);26     for(i=1;i<=n;i++){27         scanf("%lf%lf",&a[i].k,&a[i].b);28         a[i].id=i;29     }30     sort(a+1,a+n+1,cmp);31     for(i=1;i<=n;i++){32         while(top && a[i].k-a[st[top]].k<eps)top--;33         while(top>1 && cross(st[top-1],st[top])>=cross(st[top],i))top--;34         st[++top]=i;35     }36     int ans[mxn];37     for(i=1;i<=top;i++){38         ans[i]=a[st[i]].id;39     }40     sort(ans+1,ans+top+1);41     for(i=1;i<=top;i++)printf("%d ",ans[i]);42     return 0;43 }