Cod sursa(job #1516775)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 3 noiembrie 2015 16:09:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define x second
#define y first
using namespace std;

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

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

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

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

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

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

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

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

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

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