Cod sursa(job #2877385)

Utilizator francescom_481francesco martinut francescom_481 Data 24 martie 2022 18:14:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define cin fin
#define cout fout

#define N 120005
struct pct
{
    double x, y;
}v[N];
vector < pct > p;
double jos, stanga;
int ind, n;

double cros(pct x, pct y, pct z)
{
    return (y.x-x.x)*(z.y-x.y) - (z.x-x.x)*(y.y-x.y);
}
bool cmp(pct x, pct y)
{
    return (cros(v[1],x,y) < 0);
}

int main()
{
    cin >> n;
    jos = stanga = 1000000000;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> v[i].x >> v[i].y;
        if(v[i].y < jos)
        {
            jos = v[i].y;
            stanga = v[i].x;
            ind = i;
        }
        else if(v[i].y == jos)
        {
            if(v[i].x < stanga)
            {
                stanga = v[i].x;
                ind = i;
            }
        }
    }
    swap(v[1],v[ind]);
    sort(v+2,v+n+1,cmp);
    p.push_back(v[1]);
    p.push_back(v[2]);
    for(int i = 3 ; i <= n ; i++)
    {
        while(p.size() >= 2  &&  cros(p[p.size()-2],p[p.size()-1],v[i]) > 0)
        {
            p.pop_back();
        }
        p.push_back(v[i]);
    }
    cout << p.size() << '\n';
    int t = p.size();
    while(t != 0)
    {
        cout << fixed << setprecision(9) << p[t-1].x << " " << p[t-1].y << '\n';
        t--;
    }
    return 0;
}