想了一下，又看看黄大神的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;
}
评论 (0)
