Cod sursa(job #1489210)

Utilizator DeltaMTP Dragos DeltaM Data 20 septembrie 2015 19:23:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
#include<algorithm>
#define eps 0.00000001
using namespace std;
struct pct{
    double x;
    double y;
}v[130100],aux;
int n,i,j,nr,p,s[130100];
double xmin,ymin,xa,ya;
FILE *f,*g;
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<eps)
        return 1;
    return 0;
}
int cmp(pct a,pct b){
    return verif(a,b,v[1]);
}
int main(){
    f=fopen("infasuratoare.in","r");
    g=fopen("infasuratoare.out","w");
    fscanf(f,"%d",&n);
    xmin=ymin=1000000000;
    for(i=1;i<=n;i++){
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
        if(v[i].x<xmin){
            xmin=v[i].x;
            p=i;
        }
        else if(v[i].x==xmin&&v[i].y<v[p].y)
            p=i;
    }
    aux=v[1];
    v[1]=v[p];
    v[p]=aux;
    sort(v+2,v+n+1,cmp);
    s[1]=n;
    s[2]=n-1;
    nr=2;
    for(i=n-2;i>=1;i--){
        while( verif( v[ s[nr-1] ] , v[  s[nr] ] , v[i] ) )
            nr--;
        s[++nr]=i;
    }
    fprintf(g,"%d\n",nr);
    for(i=1;i<=nr;i++){
        fprintf(g,"%.6lf %.6lf\n",v[ s[i] ].x,v[ s[i] ].y);
    }
    fclose(f);
    fclose(g);
    return 0;
}