Cod sursa(job #1673237)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 3 aprilie 2016 16:23:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define inf 1999999999

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
    double x, y;
    double panta; // panta dreptei formate de punctul v[i] si colt
}v[120005], colt;
int stiva[120005], vf, n, i, poz;

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

bool convex(punct a, punct b, punct c)
{
    return ((a.x-c.x)*(b.y-a.y) + (a.x-b.x)*(a.y-c.y)) > 0;
}

int main()
{
    colt.x = colt.y = inf;
    f >> n;
    for (i = 1; i <= n; i++)
    {
        f >> v[i].x >> v[i].y;
        if (v[i].x < colt.x || (v[i].y < colt.y && v[i].x == colt.x))
            colt = v[i], poz = i;
    }

    swap(v[poz], v[1]);

    for (i = 2; i <= n; i++)
        v[i].panta = (v[i].y - colt.y)/(v[i].x - colt.x);

    sort(v+2, v+n+1, cmp);

    stiva[1] = 1, stiva[2] = 2, vf = 2;
    for (i = 3; i <= n; i++)
    {
        while (convex(v[stiva[vf-1]], v[stiva[vf]], v[i]) == 0 && vf > 2)
            vf--;
        vf++, stiva[vf] = i;
    }
    g << vf << '\n';
    for (i = 1; i <= vf; i++)
        g <<fixed << setprecision(6) << v[stiva[i]].x << " " << v[stiva[i]].y << '\n';
    return 0;
}