Cod sursa(job #1379975)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 6 martie 2015 20:46:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <stack>
#include <algorithm>

#define NMAX 120005

using namespace std;

pair <double, double> P[NMAX], stiva[NMAX];
int N, vf = 2;

void citire()
{
    scanf("%d", &N);

    for (int i = 1; i <= N; ++i)
        scanf("%lf %lf", &P[i].first, &P[i].second);
}

inline double determinant(pair <double, double> A, pair <double, double> B, pair <double, double> C)
{
    return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}

inline int cmp(const pair <double, double>& A, const pair <double, double>& B)
{
    return determinant(P[1], A, B) < 0;
}

void infasuratoare()
{
    sort(P + 1, P + N + 1);
    sort(P + 2, P + N + 1, cmp);
    stiva[1] = P[1];
    stiva[2] = P[2];

    for (int i = 3; i <= N; ++i)
    {
        while (vf >= 2 && determinant(stiva[vf - 1], stiva[vf], P[i]) > 0)
            vf--;
        stiva[++vf] = P[i];
    }
}

void afisare()
{
    printf("%d\n", vf);

    for (int i = vf; i >= 1; --i)
        printf("%.9lf %.9lf\n", stiva[i].first, stiva[i].second);
}

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

    citire();
    infasuratoare();
    afisare();

    return 0;
}