Cod sursa(job #3133644)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 26 mai 2023 14:55:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
int n;
struct puncte
{
    double x, y;
}v[10001];
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;
    for(int i = 1; i <= n; ++ i)
    {
        fin >> v[i].x >> v[i].y;
        if(i > 1)
            if(v[i].x < v[1].x)
                swap(v[i], 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)
    {
        if(!hull.empty() and arie(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) <= 0)
            hull.pop_back();
        hull.push_back(v[i]);
    }
    while(!hull.empty())
    {
        fout << fixed << setprecision(12) << hull.back().x << ' ' << hull.back().y << '\n';
        hull.pop_back();
    }
    return 0;

}