Cod sursa(job #2916482)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 30 iulie 2022 00:15:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
/// Preset de infoarena
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int maxN = 120005;
int n, k;
struct point {
    double x, y;
    bool operator < (const point &other) const {
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
}pct[maxN], v[maxN];

double arie(point a, point b, point c)
{
    /// ax ay 1 )
    /// bx by 1  ) => A = ax * by + bx * cy + cx * ay - ax * cy - bx * ay - cx * by
    /// cx cy 1 )
    return a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - a.y * b.x - a.x * c.y;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> pct[i].x >> pct[i].y;
    sort(pct + 1, pct + n + 1);
    vector <point> sus, jos;
    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();
        sus.push_back(pct[i]);
        while(jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1], pct[i]) <= 0)
            jos.pop_back();
        jos.push_back(pct[i]);
    }
    sus.pop_back();
    reverse(sus.begin(), sus.end());
    sus.pop_back();
    for(auto elem : jos)
        v[++k] = elem;
    for(auto elem : sus)
        v[++k] = elem;
    fout << k << '\n';
    fout << setprecision(12) << fixed;
    for(int i = 1; i <= k; i++)
        fout << v[i].x << ' ' << v[i].y << '\n';
    return 0;
}