Cod sursa(job #1623844)

Utilizator IgorDodonIgor Dodon IgorDodon Data 1 martie 2016 22:11:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<stdio.h>
#include<algorithm>
#define DIM 120005
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");

using namespace std;

struct Punct{ double x, y; };

int N, hST;
Punct v[DIM], ST[DIM];

bool Arie( Punct A, Punct B, Punct C ){

    double arie = A.x * B.y + B.x * C.y + C.x * A.y
                - B.x * A.y - C.x * B.y - A.x * C.y;
    if( arie > 0 ) return 1;
    return 0;

}

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

void Citire(){
int i, iFIX;
Punct FIX;

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

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

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

        if( i == 1 )
            { FIX = v[i]; iFIX = i; }

        else if( v[i].x < FIX.x || ( v[i].x == FIX.x && v[i].y < FIX.y ) )
            { FIX = v[i]; iFIX = i; }
    }

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

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

}

void Creare(){
int i;

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

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

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

        ST[++hST] = v[i];

    }

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

}

int main(){

    Citire();
    Creare();

return 0;
}