10
10
2015
0

[BZOJ1007] [HNOI2008] 水平可见直线

想了一下,又看看黄大神的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;
}
Category: BZOJ | Tags: OI | Read Count: 543

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com