[BZOJ1007]水平可见直线

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define maxn 50005
 5 #define esp 1e-8
 6 struct node{
 7     double a,b;
 8     int id;
 9 }V[maxn];
10 double a[maxn],b[maxn];
11 int sta[maxn],top;
12 bool fail(int x){
13     int l1=sta[top-1],l2=sta[top];
14     return (b[l2]-b[x])/(a[x]-a[l2])<=(b[l2]-b[l1])/(a[l1]-a[l2]);
15 }
16 bool cmp(node x,node y){
17     if(fabs(x.a-y.a)<esp)return x.b<y.b;
18     else return x.a<y.a;
19 }
20 int main(){
21     int n;
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++){
24         scanf("%lf%lf",&a[i],&b[i]);
25         V[i]=(node){a[i],b[i],i};
26     }
27     sort(V+1,V+1+n,cmp);
28     if(n==1)printf("1 \n");
29     else if(n==2){
30         if(V[1].a==V[2].a)printf("1 \n");
31         else printf("1 2 \n");
32     }
33     else{
34         for(int i=1;i<=n;i++){
35             int yo=V[i].id;
36             while(top){
37                 if(fabs(a[sta[top]]-a[yo])<esp)top--;
38                 else if(top>1&&fail(yo))top--;
39                 else break;
40             }
41             sta[++top]=yo;
42         }
43         sort(sta+1,sta+1+top);
44         for(int i=1;i<=top;i++)
45             printf("%d ",sta[i]);
46         printf("\n");
47     }
48     return 0;
49 }