Cod sursa(job #2209303)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 2 iunie 2018 18:00:51
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

#define X first
#define Y second
#define eps 1e-12

using namespace std;

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

vector<pair<double, double>> pct;
int N, k, st[240003], selected[120003];
double x, y;

inline int cmp(double a, double b)
{
    if (a + eps < b) return -1;
    if (b + eps < a) return 1;
    return 0;
}

inline int det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    return cmp(a.X * b.Y + b.X * c.Y + c.X * a.Y - a.Y * b.X - b.Y * c.X - c.Y * a.X, 0.0);
}

int main()
{
    f >> N;
    pct.emplace_back(0, 0);
    for(int i = 1; i <= N; i++) {
        f >> x >> y;
        pct.emplace_back(x, y);
    }

    sort(pct.begin(), pct.end());
    st[++k] = 0;
    st[++k] = 1;
    selected[1] = true;
    int i = 2, pas = 1;
    while(!selected[0]) {
        while(selected[i]) {
            if(i == N - 1) pas = -1;
            i += pas;
        }
        while(k >= 2 && det(pct[st[k]], pct[st[k - 1]], pct[i]) == -1) {
            selected[st[k]] = false;
            k--;
        }
        st[++k] = i;
        selected[i] = true;
    }
    g << k - 1 << "\n" << setprecision(6) << fixed;
    for(int it = k - 1; it >= 1; it--) {
        auto aux = pct[st[it]];
        g << aux.X << " " << aux.Y << "\n";
    }
    return 0;
}