Cod sursa(job #1688935)

Utilizator IgorDodonIgor Dodon IgorDodon Data 13 aprilie 2016 20:08:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<algorithm>
#define MAXN 120005
#define MAXD 1000000000
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");

using namespace std;

struct Punct{ double x, y; } v[MAXN], t;

int N, ST[MAXN], hST;

bool Arie( Punct A, Punct B, Punct C ){
double arie;

    arie = A.x * B.y + B.x * C.y + C.x * A.y
         - A.y * B.x - B.y * C.x - C.y * A.x;

    if( arie > 0 )
        return 1;
        return 0;

}

bool cmp( Punct A, Punct B ){ return Arie( v[1], A, B ); }

void Citire(){
int i, xmin = MAXD, ymin = MAXD, imin;

    fscanf(f,"%d\n",&N);

    for(i=1;i<=N;i++){

        fscanf(f,"%lf %lf\n",&v[i].x,&v[i].y);

        if( v[i].x < xmin || ( v[i].x == xmin && v[i].y < ymin ) ){

            xmin = v[i].x;
            ymin = v[i].y;
            imin = i;

        }

    }

    if( imin != 1 )
        swap( v[1], v[imin] );

    sort(v+2,v+N+1,cmp);

}

void Rezolvare(){
int i;

    ST[1] = 1;
    ST[2] = 2;
    hST = 2;

    for(i=3;i<=N;i++){

        while( !Arie( v[ ST[hST-1] ], v[ ST[hST] ], v[i] ) && hST > 2 )
            hST--;

        ST[++hST] = i;

    }

    fprintf(g,"%d\n",hST);
    for(i=1;i<=hST;i++)
        fprintf(g,"%.6lf %.6lf\n",v[ ST[i] ].x,v[ ST[i] ].y);

}

int main(){

    Citire();
    Rezolvare();

return 0;
}