Cod sursa(job #1515456)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 1 noiembrie 2015 17:21:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define x second
#define y first
using namespace std;

ifstream is("infasuratoare.in");
ofstream os("infasuratoare.out");

int n, m;
vector<pair<double, double>> p, a;

void Read();
void Sort();
void Write();
void ConvexHull();

inline double CrossProduct(const pair<double, double>& a, const pair<double, double>& b, const pair<double, double>& c)
{
    return ( a.x - b.x ) * ( a.y - c.y ) - ( a.x - c.x ) * ( a.y - b.y );
}

inline bool Cmp(const pair<double, double>& a, const pair<double, double>& b)
{
    return CrossProduct(p[1], a, b) > 0;
}

int main()
{
    Read();
    Sort();
    ConvexHull();
    Write();
    is.close();
    os.close();
    return 0;
}

void ConvexHull()
{
    a[1] = p[1];
    a[2] = p[2];
    m = 2;
    for ( int i = 3; i <= n; ++i )
    {
        while ( m >= 2 && CrossProduct(a[m - 1], a[m], p[i]) < 0 )
            --m;
        a[++m] = p[i];
    }
}

void Write()
{
    os << m << "\n";
    for ( int i = 1; i <= m; ++i )
        os << fixed << setprecision(9) << a[i].x << " " << a[i].y << "\n";
}

void Sort()
{
    for ( int i = 2; i <= n; ++i )
        if ( p[1] > p[i] )
            swap(p[1], p[i]);
    sort(p.begin() + 2, p.begin() + n + 1, Cmp);
}

void Read()
{
    is >> n;
    a = p = vector<pair<double, double>>(n + 1);
    for ( int i = 1; i <= n; ++i )
        is >> p[i].x >> p[i].y;
}