Cod sursa(job #3200090)

Utilizator pifaDumitru Andrei Denis pifa Data 3 februarie 2024 14:58:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int max_size = 12e4 + 1;

pair <double, double> pct[max_size];
vector <pair <double, double>> sus, jos, ans;

double arie (pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
    return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}

int main ()
{
    int n;
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> pct[i].first >> pct[i].second;
    }
    sort(pct + 1, pct + n + 1);
    sus.push_back(pct[1]);
    jos.push_back(pct[1]);
    for (int i = 2; i <= n; i++)
    {
        while (sus.size() > 1 && arie(sus[sus.size() - 2], sus[sus.size() - 1], pct[i]) >= 0)
        {
            sus.pop_back();
        }
        while (jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1], pct[i]) <= 0)
        {
            jos.pop_back();
        }
        sus.push_back(pct[i]);
        jos.push_back(pct[i]);
    }
    sus.pop_back();
    reverse(sus.begin(), sus.end());
    sus.pop_back();
    for (auto f : jos)
    {
        ans.push_back(f);
    }
    for (auto f : sus)
    {
        ans.push_back(f);
    }
    out << ans.size() << '\n';
    out << fixed << setprecision(6);
    for (auto f : ans)
    {
        out << f.first << " " << f.second << '\n';
    }
    in.close();
    out.close();
    return 0;
}