Cod sursa(job #1597635)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 12 februarie 2016 10:40:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NMAX 120005
#define eps 0.000000000001

using namespace std;

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

int i, n, m = 0;

struct punct
{
    double x, y, panta;
}v[NMAX], stiva[NMAX];

double det(punct a, punct b, punct c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - a.y * b.x - a.x * c.y;
}

bool cmp(punct a, punct b)
{
    return det(v[1], a, b) < 0;
}

bool cmp2(punct a, punct b)
{
    if (fabs(a.x - b.x) < eps)
        return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    f >> n;

    for (i = 1; i <= n; ++ i)
        f >> v[i].x >> v[i].y;

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

    stiva[++ m] = v[1];
    stiva[++ m] = v[2];

    for (i = 3; i <= n; ++ i)
    {
        while (m >= 3 && det(stiva[m], stiva[m - 1], v[i]) < 0)
            m --;
        stiva[++ m] = v[i];
    }

    g << m << '\n';

    g << fixed << setprecision(12);

    for (i = m; i >= 1; -- i)
        g << stiva[i].x << " " << stiva[i].y << '\n';

    return 0;
}