Cod sursa(job #2871138)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 12 martie 2022 21:39:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

const string filename = "infasuratoare";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

#define cx first
#define cy second

const int eps = 1e-6;
int n;
pair <double, double> pct[120005];
vector <int> sus, jos, ans;

double arie(int a, int b, int c)
{
    /// ax ay 1
    /// bx by 1  => ax * by + bx * cy + cx * ay - ax * cy - bx * ay - cx * by
    /// cx cy 1
    return pct[a].cx * pct[b].cy + pct[a].cy * pct[c].cx + pct[b].cx * pct[c].cy - pct[b].cy * pct[c].cx - pct[a].cy * pct[b].cx - pct[a].cx * pct[c].cy;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> pct[i].cx >> pct[i].cy;
    sort(pct + 1, pct + n + 1);
    sus.push_back(1);
    jos.push_back(1);
    for(int i = 2; i <= n; i++)
    {
        while(sus.size() > 1 && arie(sus[sus.size() - 2], sus[sus.size() - 1],  i) > 0)
            sus.pop_back();
        sus.push_back(i);
        while(jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1],  i) < 0)
            jos.pop_back();
        jos.push_back(i);
    }
    fout << sus.size() + jos.size() - 2 << '\n';
    for(int ind : jos)
        ans.push_back(ind);
    for(int i = sus.size() - 1; i >= 0; i--)
    {
        int ind = sus[i];
        if(ind != 1 && ind != n)
            ans.push_back(ind);
    }
    fout << setprecision(12) << fixed;
    for(int ind : ans)
        fout << pct[ind].cx << ' ' << pct[ind].cy << '\n';
    return 0;
}