Cod sursa(job #2208833)

Utilizator amaliarebAmalia Rebegea amaliareb Data 31 mai 2018 19:34:14
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double, double> point;
vector<point> v;

int n, m, szt, szb;
set<point> top, bot;

double det(point a, point b, point c) {
    return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}

void CHull(vector<point> v) {
    sort(v.begin(), v.end());

    for (auto p: v) {
        while (szt >= 2 && det(*prev(prev(top.end())), *prev(top.end()), p) >= 0)
            top.erase(prev(top.end())), --szt;
        top.insert(p);
        ++szt;

        while (szb >= 2 && det(*prev(prev(bot.end())), *prev(bot.end()), p) <= 0)
            top.erase(prev(bot.end())), --szb;
        bot.insert(p);
        ++szb;
    }
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; ++i) {
        double x, y;
        f >> x >> y;
        v.push_back({x, y});
    }
    CHull(v);
    g << top.size() + bot.size() - 2 << '\n';
    for (auto a: top) g << fixed << setprecision(10) << a.x << ' ' << a.y << '\n';
    auto it = prev(bot.end());
    while (it != next(bot.begin())) {
        --it;
        g << fixed << setprecision(10) << it->x << ' ' << it->y << '\n';
    }
    return 0;
}