Cod sursa(job #1703624)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 17 mai 2016 11:45:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

const int DIM = 1 << 17;
const double EPS = 0.000000000001;
using namespace std;

int N, K, S[DIM];
struct point{ double x, y; } P[DIM];

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

inline bool cmp( point A, point B ) {
    return cross_product( P[1], A, B ) < 0;
}

int main() {

    FILE *input_file  = fopen( "infasuratoare.in" , "r" );
    FILE *output_file = fopen( "infasuratoare.out", "w" );

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

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

        if( P[i].x < P[1].x )
            swap( P[1], P[i] );
        else
        if( fabs( P[i].x - P[1].x ) < EPS ) {
            if( P[i].y < P[1].y )
                swap( P[1], P[i] );
        }
    }

    sort( P + 2, P + N + 1, cmp );
    S[++K] = 1; S[++K] = 2;

    for( int i = 3; i <= N; i ++ ) {
        while( K >= 2 && cross_product( P[ S[K - 1] ], P[ S[K] ], P[i] ) > 0 )
            K --;
        S[++K] = i;
    }

    fprintf( output_file, "%d\n", K );

    for( int i = 1; i <= K; i ++ )
        fprintf( output_file, "%.12lf %.12lf\n", P[ S[i] ].x, P[ S[i] ].y );

    return 0;
}