Cod sursa(job #1461465)

Utilizator CollermanAndrei Amariei Collerman Data 15 iulie 2015 19:19:49
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ofstream fout("infasuratoare.out");
ifstream fin("infasuratoare.in");
const int NMAX = 120005;
const double EPS = 1e-12;

int n, lg, H;
struct punct { double x, y; } p[NMAX];
punct sol[NMAX];

bool cmp(punct a, punct b) { return a.x < b.x; }

void citire()
{
    fin >> n;
    for(int i=1; i<=n; i++) fin >> p[i].x >> p[i].y;
}

void afis()
{
    fout << lg << '\n';
    for(int i=2; i<=lg+1; i++)
        fout << setprecision(6) << fixed << sol[i].x << ' ' << sol[i].y << '\n';
}

int cross_product(punct det, punct a, punct b)
{
    return (a.x - det.x) * (b.y - det.y) - (b.x - det.x) * (a.y - det.y);
}

void convex_hull()
{
    sort(p + 1, p + n + 1, cmp);

    for(int i=1; i<=n; i++) {
        while(lg > 1 && cross_product(sol[lg-1], sol[lg], p[i]) < EPS)
            lg--;
        sol[++lg] = p[i];
    }

    for(int i=n, t=lg+1; i; i--) {
        while(lg >= t && cross_product(sol[lg-1], sol[lg], p[i]) < EPS)
            lg--;
        sol[++lg] = p[i];
    }
    lg--;
}

int main()
{
    citire();
    convex_hull();
    afis();
    return 0;
}