想了一下,又看看黄大神的blog,然后就水掉了这题……
具体请看hzwer's blog:点击此处
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; int n,flg[50005],ST; struct Node{ double a,b; int i; }a[50005],s[50005]; int cmp(Node sa,Node sb){ if(fabs(sa.a-sb.a)<=0.0000001)return sa.b<sb.b; return sa.a<sb.a; } double SetX(Node x,Node y){ return (y.b-x.b)/(x.a-y.a); } void Insert(int x){ while(ST){ if(fabs(s[ST].a-a[x].a)<=0.0000001)ST--; else if(ST>1 && SetX(a[x],s[ST-1])<=SetX(s[ST],s[ST-1])){ ST--; } else break; } s[++ST]=a[x]; } int main(){ freopen("1007.in","r",stdin); freopen("1007.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf %lf",&a[i].a,&a[i].b); a[i].i=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++)Insert(i); for(int i=1;i<=ST;i++)flg[s[i].i]=1; for(int i=1;i<=n;i++)if(flg[i])printf("%d ",i); return 0; }