Cod sursa(job #1064660)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 22 decembrie 2013 10:47:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

const int Nmax = 120001;

struct Point
{
    double x;
    double y;

    bool operator < ( const Point &A ) const
    {
        if ( x == A.x )
                return y < A.y;
        else
                return x < A.x;
    }
};

Point points[Nmax];
Point stiva[Nmax];
int N, head;

double Cross_Product( Point A, Point B, Point C )
{
    return ( B.x - A.x ) * ( C.y - A.y ) -
           ( B.y - A.y ) * ( C.x - A.x );
}

int cmp( Point A, Point B )
{
    return ( Cross_Product( points[1], A, B ) < 0 );
}

void SortPoints()
{
    for ( int i = 2; i <= N; ++i )
    {
        if ( points[1] < points[i] )
                swap( points[1], points[i] );
    }

    sort( points + 2, points + N + 1, cmp );
}

void GrahamScan()
{
    stiva[ ++head ] = points[1];
    stiva[ ++head ] = points[2];

    for ( int i = 3; i <= N; ++i )
    {
        while ( head >= 2 && Cross_Product( stiva[head - 1], stiva[head], points[i] ) > 0 )
                    head--;

        stiva[ ++head ] = points[i];
    }
}

void read()
{
    ifstream f("infasuratoare.in");

    f >> N;

    for ( int i = 1; i <= N; ++i )
    {
        f >> points[i].x >> points[i].y;
    }
}

void print()
{
    ofstream g("infasuratoare.out");

    g << head << "\n";

    for ( int i = head; i >= 1; i-- )
    {
        g << fixed << setprecision( 10 );
        g << stiva[i].x << " " << stiva[i].y << "\n";
    }
}

int main()
{
    read();
    SortPoints();
    GrahamScan();
    print();

    return 0;
}