Cod sursa(job #3225560)

Utilizator MAlex2019Melintioi George Alexandru MAlex2019 Data 17 aprilie 2024 22:54:11
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <list>

using namespace std;
using point=pair<double,double>;

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

const int MAXN = 12e4;
point v[MAXN + 1];
point *O = v;

bool cmp(point &A, point &B) {
    if (A.first == B.first)
        return A.second < B.second;
    return A.first < B.first;
}

double cmpcrossProduct(point A, point B) {
    point AO = {O->first - A.first, O->second - A.second};
    point OB = {B.first - O->first, B.second - O->second};
    return AO.first * OB.second > AO.second * OB.first;
}

bool trigonometricOrder(point A, point B, point C) {
    point AB = {B.first - A.first, B.second - A.second};
    point BC = {C.first - B.first, C.second - B.second};
    return AB.first * BC.second > AB.second * BC.first;
}

ostream& operator<<(ostream &os, const point &a) {
    os << a.first << ' ' << a.second;
    return os;
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    int n;
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i].first >> v[i].second;
    sort(v, v + n, cmp);
    sort(v + 1, v + n, cmpcrossProduct);
    v[n] = v[0];

    list<point> poli;
    poli.push_back(*O);
    for (int i = 1; i < n; i++) {
        while (i < n && trigonometricOrder(*poli.rbegin(), v[i], v[i + 1]))
            i++;
        poli.push_back(v[i]);
    }
    while (true) {
        bool stop = true;
        auto itr = poli.begin();
        for (++itr; itr != prev(poli.end()); itr++)
            if (trigonometricOrder(*prev(itr), *itr, *next(itr))) {
                itr = prev(poli.erase(itr));
                stop = false;
            }
        if (stop)
            break;
    }
    reverse(next(poli.begin()), poli.end());
    fout << poli.size() << '\n';
    for (point elem: poli)
        fout << fixed << setprecision(14) << elem << '\n';

    return 0;
}