Cod sursa(job #1934338)

Utilizator AndreiGrigorasAndrei Grigoras AndreiGrigoras Data 21 martie 2017 13:21:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
#define MAX_N 120005

using namespace std ;

ifstream fin ( "infasuratoare.in" ) ;
ofstream fout ( "infasuratoare.out" ) ;

struct Point
{
    double x ;
    double y ;
} v[MAX_N] ;


int N, head ;
Point stk[MAX_N] ;

void read()
{
    fin >> N ;
    for ( int i = 1 ; i <= N ; ++i )
        fin >> v[i].x >> v[i].y ;
}

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

inline int cmp(const Point& p1, const Point& p2)
{
    return cross_product(v[1], p1, p2) < 0;
}

void sort_points()
{
    int pos = 1;
    for ( int i = 2 ; i <= N ; ++i )
        if ( v[i].x < v[pos].x || ( v[i].x ==v[pos].x && v[i].y < v[pos].y ) )
            pos = i ;
    swap( v[1], v[pos] ) ;
    sort( v + 2, v + N + 1, cmp ) ;
}

void convex_hull()
{
    sort_points();

    stk[1] = v[1];
    stk[2] = v[2];
    head = 2;

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

void write()
{
    fout << fixed;
    fout << head << "\n";
    for ( int i = head ; i >= 1 ; --i )
        fout << setprecision(9) << stk[i].x << " " << stk[i].y << "\n" ;
}

int main()
{
    read() ;
    convex_hull() ;
    write() ;
}