Cod sursa(job #1117511)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 23 februarie 2014 16:52:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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;
} v[DIM];

long int n, st[DIM], Hst;

void citire(){
long int i, imin=1;

    fscanf(f,"%ld\n",&n);
    for(i=1;i<=n;i++){
        fscanf(f,"%lf %lf\n",&v[i].x,&v[i].y);
        if( v[i].x < v[imin].x || ( v[i].x == v[imin].x && v[i].y < v[imin].y ) ) imin=i;
    }
    swap( v[imin], v[1] ); // nu sunt singur ca merge cand imin=1

}

bool arie( punct A, punct B, punct 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

}

bool cmp( punct K1, punct K2 ){ return arie(v[1],K1,K2); }

void rezolvare(){
long 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;
    }

}

void afisare(){
long int i;

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

}

int main(){

    citire();
    sort(v+2,v+n+1,cmp);
    rezolvare();
    afisare();

return 0;
}