Cod sursa(job #3156338)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 11 octombrie 2023 11:25:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

using ld = long double;

int n;
pair<ld,ld> a[120005];

ld signed_area(pair<ld,ld> x, pair<ld,ld> y, pair<ld,ld> z)
{
    ld ar = x.first * y.second - x.second * y.first + y.first * z.second - y.second * z.first + z.first * x.second - z.second * x.first;
    return ar;
}

bool cmp(pair<ld,ld> A, pair<ld,ld> B)
{
    return signed_area(a[1],A,B) < 0;
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; i++)
        in >> a[i].first >> a[i].second;
    for (int i = 2; i <= n; i++)
        if (a[i] < a[1])
            swap(a[1],a[i]);
    sort(a + 2,a + n + 1,cmp);
    vector<pair<ld,ld>>stk = {a[1],a[2]};
    for (int i = 3; i <= n; i++)
    {
        while (stk.size() >= 2 and signed_area(stk[stk.size() - 2],stk[stk.size() - 1],a[i]) > 0)
            stk.pop_back();
        stk.push_back(a[i]);
    }
    out << setprecision(12) << fixed;
    out << stk.size() << '\n';
    while (!stk.empty())
        out << stk.back().first << ' ' << stk.back().second << '\n',stk.pop_back();
    return 0;
}