Cod sursa(job #3133849)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 27 mai 2023 11:16:28
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
int n;
struct puncte
{
    double x, y;
}v[120001];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double arie(puncte &a, puncte &b, puncte &c)
{
    return a.x*b.y + b.x*c.y + c.x*a.y -a.y*b.x - b.y*c.x - c.y*a.x;
}
bool cmp(puncte &a, puncte &b)
{
    return arie(v[1], a, b) > 0;
}
vector<puncte> hull;
int main()
{
    fin >> n;
    int ind = 0;
    for(int i = 1; i <= n; ++ i)
    {
        fin >> v[i].x >> v[i].y;
        if(i > 1)
            if(v[i].x < v[1].x)
                ind = i;
            else if(v[i].x == v[1].x and v[i].y < v[1].y)
                ind = i;
    }
    swap(v[ind], v[1]);
    sort(v + 2, v + n + 1, cmp);
    hull.push_back(v[1]);
    hull.push_back(v[2]);
    for(int i = 3; i <= n; ++ i)
    {
        while(hull.size() > 1 and arie(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) <= 0)
            hull.pop_back();
        hull.push_back(v[i]);
    }
    fout << hull.size() << '\n';
    for(auto it : hull)
    {
        fout << fixed  << setprecision(12) << it.x << ' ' << it.y << '\n';
    }
    return 0;

}