Cod sursa(job #1110359)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 17 februarie 2014 23:44:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct pct{
    double x;
    double y;
}v[150000];
int n,i,j,st[150000],nr;
FILE *f,*g;
int cmp(pct a,pct b){
    double x=a.x*b.y-a.y*b.x;
    if(x<0)
        return 0;
    return 1;
}
int verif(pct a,pct b,pct c){
    double x=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
    if(x<=0.000000000001)
        return 0;
    return 1;
}
int main(){
    f=fopen("infasuratoare.in","r");
    g=fopen("infasuratoare.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
    }
    sort(v+1,v+n+1,cmp);
    st[1]=1;
    st[2]=2;
    nr=2;
    for(i=3;i<=n;i++){
        if(verif(v[st[nr-1]],v[st[nr]],v[i])==0&&nr>=2)
            nr--;
        st[++nr]=i;
    }
    fprintf(g,"%d\n",nr);
    for(i=1;i<=nr;i++){
        fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
    }

    fclose(f);
    fclose(g);
    return 0;
}