Cod sursa(job #1377702)

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

using namespace std;

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

long int N;
long int ST[MAXN], HST;

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

    double arie = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
    if( arie > 0  ) return 0;   // sens orar
    return 1;                   // sens trigonometric

}

void Citire(){
long int i, imin;
Puncte minim;

    fscanf(f,"%ld\n",&N);
    for(i=1;i<=N;i++){

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

        if(i==1){ imin = i; minim = v[i]; }
        else if( v[i].x < minim.x || ( v[i].x == minim.x && v[i].y < minim.y ) ){
             minim = v[i];
             imin = i;
        }
    }
    swap( v[1], v[imin] );

}

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

void Rezolvare(){
long int i;

    ST[1]=1; ST[2]=2; HST=2;
    for(i=3;i<=N;i++){

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

    fprintf(g,"%ld\n",HST);
    for(i=HST;i>=1;i--)
        fprintf(g,"%.6lf %.6lf\n",v[ST[i]].x,v[ST[i]].y);

}

int main(){

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

return 0;
}