Cod sursa(job #2107263)

Utilizator papinub2Papa Valentin papinub2 Data 16 ianuarie 2018 22:02:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

const int Nmax = 120005;

struct punct
{
    double x;
    double y;
}v[Nmax];

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

double intoarcere (int P0, int P1, punct P2)
{
    return (v[P1].x - v[P0].x) * (P2.y - v[P0].y) - (P2.x - v[P0].x) * (v[P1].y - v[P0].y);
}

int main()
{
    int n, varf = 0;
    vector<int> Q(Nmax);
    vector<bool> viz(Nmax);

    in >> n;

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

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

    Q[++varf] = 1;
    Q[++varf] = 2;
    viz[2] = 1;

    for (int i = 3; i <= n; i++)
    {
        while (varf > 1 && intoarcere(Q[varf - 1], Q[varf], v[i]) <= 0)
        {
            viz[Q[varf]] = 0;
            varf--;
        }

        viz[i] = 1;
        Q[++varf] = i;
    }

    const int nr = varf;

    for (int i = n - 1; i >= 1; i--)
    {
        if (viz[i]) continue;
        while (varf > nr && intoarcere(Q[varf - 1], Q[varf], v[i]) <= 0)
        {
            viz[Q[varf]] = 0;
            varf--;
        }

        viz[i] = 1;
        Q[++varf] = i;
    }

    out << varf - 1 << '\n';
    for (int i = 1; i < varf; i++)
        out << fixed << setprecision(12) << v[Q[i]].x << ' ' << v[Q[i]].y << '\n';
    return 0;
}