Cod sursa(job #1087465)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 19 ianuarie 2014 14:14:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <algorithm>

#define Nmax 120005

using namespace std;

struct Punct
{
    double x, y;
};

int N, Stiva[Nmax], vf = 2, Used[Nmax];
Punct P[Nmax];

bool Comp(Punct A, Punct B)
{
    if (A.y == B.y)
        return A.x < B.x;
    return A.y < B.y;
}

void Citire()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf("%lf%lf", &P[i].x, &P[i].y);
    sort(P + 1, P + N + 1, Comp);
    Stiva[1] = 1;
    Stiva[2] = 2;
    Used[1] = Used[2] = 1;
}

bool Determinant(Punct A, Punct B, Punct C)
{
    if (A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - B.x * A.y - A.x * C.y > 0)
        return true;
    return false;
}

void Infasuratoare()
{
    for (int i = 3; i <= N; ++i)
    {
        while (!Determinant(P[Stiva[vf - 1]], P[Stiva[vf]], P[i]) && vf > 1)
            Used[Stiva[vf--]] = 0;
        Stiva[++vf] = i;
        Used[Stiva[vf]] = 1;
    }
    Used[1] = 0;
    for(int i = N; i >= 1; --i)
        if(!Used[i])
        {
            while (!Determinant(P[Stiva[vf - 1]], P[Stiva[vf]], P[i]) && vf > 1)
                Used[Stiva[vf--]] = 0;
            Stiva[++vf] = i;
            Used[Stiva[vf]] = 1;
        }
}

void Afisare()
{
    vf--;
    printf("%d\n", vf);
    for (int i = 1; i <= vf; ++i)
        printf("%.6lf %.6lf\n", P[Stiva[i]].x, P[Stiva[i]].y);
}

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

    Citire();
    Infasuratoare();
    Afisare();

    return 0;
}