Cod sursa(job #942824)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 23 aprilie 2013 17:34:47
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <vector>

using namespace std;

#define Nmax 120005
#define eps 1e-12
#define ox first
#define oy second

const char FileIn[] =  { "infasuratoare.in"  };
const char FileOut[] = { "infasuratoare.out" };

typedef pair<double, double> Point;

Point v[Nmax], poligon[Nmax];
bitset <Nmax> viz;
int ST[Nmax];

int N, vf, head;

void citire(){

    ifstream f(FileIn);

    f >> N;

    for ( int i = 1; i <= N; i++ )
        f >> v[i].ox >> v[i].oy;

    f.close();
}

double Cross_Product( Point O, Point A, Point B ){

    return ( A.ox - O.ox ) * ( B.oy - O.oy ) - ( B.ox - O.ox ) * ( A.oy - O.oy );
}

void Convex_Hull(){

    ST[ ++head ] = 1;
    ST[ ++head ] = 2;

    viz[2] = true;

    for ( int i = 1, p = 1; i; i += ( p = ( i == N ? -p : p ) ) ){

        if ( viz[i] )
            continue;

        while( head >= 2 && Cross_Product( v[ ST[ head - 1 ] ], v[ ST[ head ] ], v[i] ) < eps )
            viz[ ST[ head-- ] ] = false;

        ST[ ++head ] = i;
        viz[i] = true;
    }

    vf = head - 1;

    for ( int i = 1; i <= vf; i++ )
        poligon[i] = v[ ST[i] ];
}

void afis(){

    ofstream g(FileOut);

    g << vf << "\n";

    for ( int i = 1; i <= vf; i++ )
        g << poligon[i].ox << " " << poligon[i].oy << "\n";

    g.close();
}

int main(){

    citire();
    sort( v + 1, v + N + 1 );
    Convex_Hull();
    afis();

    return 0;
}