HNOI 2008：水平可见直线

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

　　这道题按斜率排序后维护一个单点序列，怎么写怎么对。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 const int N=50010;
 7 struct Node{
 8   int k,b,id;
 9   friend bool operator<(Node a,Node b){
10     if(a.k!=b.k)return a.k<b.k;
11     return a.b>b.b;
12   }
13 }l[N];
14  
15 double Cx(Node a,Node b){
16   return 1.0*(a.b-b.b)/(b.k-a.k);
17 }
18  
19 int n,m;
20 int st[N],top;
21 int main(){
22   scanf("%d",&n);
23   for(int i=1;i<=n;i++){
24     scanf("%d%d",&l[i].k,&l[i].b);
25     l[i].id=i;
26   }
27   sort(l+1,l+n+1);
28   for(int i=1;i<=n;i++){
29     if(l[i].k!=l[i-1].k)
30       l[++m]=l[i];
31   }
32   n=m;
33   st[top=1]=1;
34   for(int i=2;i<=n;i++){
35     while(top>1&&Cx(l[i],l[st[top]])<=Cx(l[st[top]],l[st[top-1]]))top-=1;
36     st[++top]=i;
37   }
38   for(int i=1;i<=top;i++)
39     st[i]=l[st[i]].id;
40   sort(st+1,st+top+1);
41   for(int i=1;i<=top;i++)
42     printf("%d ",st[i]);
43   return 0;
44 }