Cod sursa(job #1375369)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 5 martie 2015 13:04:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <algorithm>
#include <stack>

#define f first
#define s second

using namespace std;

pair <double, double> v[120010];
bool frq[120010];
int st[120010];

bool det (pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
    double d = 1.0 * a.f * b.s + 1.0 * b.f * c.s + 1.0 * a.s * c.f - 1.0 * c.f * b.s - 1.0 * b.f * a.s - 1.0 * c.s * a.f;
    return (d < 0.0);
}

int main ()
{
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);

    int n;
    scanf ("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf ("%lf %lf", &v[i].f, &v[i].s);

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

    st[1] = 1;
    st[0] = st[2] = 2;
    frq[2] = true;

    int i = 3, p = 1;
    while (!frq[1])
    {
        while (frq[i])
        {
            if (i == n) p = -1;
            i += p;
        }

        while (st[0] > 1 && !det (v[st[st[0] - 1]], v[st[st[0]]], v[i]))
            frq[st[st[0]--]] = false;

        st[++st[0]] = i;
        frq[i] = true;
    }

    --st[0];
    printf ("%d\n", st[0]);

    for (int i = 1; i <= st[0]; ++i)
        printf ("%lf %lf\n", v[st[i]].f, v[st[i]].s);

    return 0;
}