Cod sursa(job #2887116)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 8 aprilie 2022 21:00:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <algorithm>

using namespace std;

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

const int maxN = 120005;
int n;
struct point {
    double cx, cy;
    bool operator < (const point &other) const
    {
        if(cx == other.cx)
            return cy < other.cy;
        return cx < other.cx;
    }
}pct[maxN];
vector <int> sus, jos, ans;

double arie(int a, int b, int c)
{
    /// ax ay 1 )
    /// bx by 1  ) => A = 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);
    }
    ans = jos;
    reverse(sus.begin(), sus.end());
    for(int ind : sus)
        if(ind != 1 && ind != n)
            ans.push_back(ind);
    fout << ans.size() << '\n';
    fout << setprecision(12) << fixed;
    for(int ind : ans)
        fout << pct[ind].cx << ' ' << pct[ind].cy << '\n';
    return 0;
}