Cod sursa(job #1438374)

Utilizator BLz0rDospra Cristian BLz0r Data 19 mai 2015 19:55:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define Nmax 120002
#define eps ( 1 / ( 1e12 ) )

FILE *f = fopen ( "infasuratoare.in", "r" );
FILE *g = fopen ( "infasuratoare.out", "w" );

struct point{
    double x, y;
} v[Nmax];

int N, L, Hull[Nmax];

bool cmp ( point A, point B ){

    if ( abs ( A.x - B.x ) < eps )
        return A.y < B.y;
    return A.x < B.x;
}

double crossp ( point A, point B, point C ){
    return A.x * ( B.y - C.y ) + B.x * ( C.y - A.y ) + C.x * ( A.y - B.y );
}

void ConvexHull(){

    for ( int i = 1; i <= N; ++i ){
        while ( L > 1 && crossp ( v[Hull[L-1]], v[Hull[L]], v[i] ) <= 0 )
            L--;
        Hull[++L] = i;
    }

    int l = L;

    for ( int i = N; i >= 1; --i ){
        while ( L > l && crossp ( v[Hull[L-1]], v[Hull[L]], v[i] ) <= 0 )
            L--;
        Hull[++L] = i;
    }
    L--;
}

int main(){

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

    for ( int i = 1; i <= N; ++i )
        fscanf ( f, "%lf%lf", &v[i].x, &v[i].y );

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

    ConvexHull();

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

    return 0;
}