Cod sursa(job #2300196)

Utilizator papinub2Papa Valentin papinub2 Data 10 decembrie 2018 22:37:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

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

struct punct
{
    double x;
    double y;
};

double intoarcere (punct A, punct B, punct C)
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

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

int main()
{
    int n, nr = 0;

    in.sync_with_stdio(false);
    in >> n;

    vector<punct> v;
    vector<int> Q(n + 1);
    vector<bool> OK(n + 1);

    for (int i = 1; i <= n; i++)
    {
        double x, y;
        in >> x >> y;
        v.push_back({x, y});
    }

    sort(v.begin(), v.end(), cmp);

    Q[++nr] = 0;
    Q[++nr] = 1;
    OK[1] = 1;

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

        Q[++nr] = i;
        OK[i] = 1;
    }

    const int lim = nr;

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

        Q[++nr] = i;
        OK[i] = 1;
    }

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

    return 0;
}