Cod sursa(job #1456590)

Utilizator petru.cehanCehan Petru petru.cehan Data 1 iulie 2015 12:19:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>

using namespace std;

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

struct Punct
{
    double x,y;
};

Punct pct[120005];
Punct ch[120005];

int n,M;

double cross_Product ( const Punct& A , const Punct& B , const Punct& C )
{
    return A.x * ( B.y - C.y ) + B.x * ( C.y - A.y ) + C.x * ( A.y - B.y ) ;
}

int comp ( const Punct& A , const Punct& B )
{
    return cross_Product ( pct[1] , A , B ) < 0;
}

void point_sort()
{
    int pos = 1; int i ;
    for ( i = 2; i <= n; ++ i )
    {
        if ( pct[i].x == pct[pos].x )
        {
            if ( pct[i].y < pct[pos].y )
            {
                pos = i;
            }
        }
        else if ( pct[i].x < pct[pos].x )
        {
            pos = i;
        }
    }

    swap ( pct[1],pct[pos] );
    sort ( pct+2 , pct+n+1 , comp );
}

void convex_hull()
{
    point_sort();
    M = 2;
    ch[1] = pct[1];
    ch[2] = pct[2];
    int i ;
    for ( i = 3; i <= n; ++i )
    {
        while ( M  >= 2 && cross_Product ( ch[M-1] , ch[M] , pct[i] ) > 0 )
                   -- M ;
        ch[++M] = pct[i];
    }
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> pct[i].x >> pct[i].y;

    convex_hull();

    fout << M << "\n";
    for(int i = M; i >= 1; i--)
        fout << fixed << setprecision(12) << ch[i].x << " " << ch[i].y << "\n";
    return 0 ;
}