Cod sursa(job #3141869)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 17 iulie 2023 12:45:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct point
{
    double x,y;
} v[200005];
double aria(point a,point b,point c)
{
    a.x-=c.x;
    a.y-=c.y;
    b.x-=c.x;
    b.y-=c.y;
    return a.x*b.y-a.y*b.x;
}
point A,B;
bool compu(point a,point b)
{
    double ar=aria(B,a,b);
    if(ar!=0)
        return ar>0;
    return a.x>b.x;
}
bool compd(point a,point b)
{
    double ar=aria(A,a,b);
    if(ar!=0)
        return ar>0;
    return a.x<b.x;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>n;
    A={2e9,2e9};
    B={-2e9,-2e9};
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(A.x>v[i].x)
            A=v[i];
        else if(A.x==v[i].x&&A.y>v[i].y)
            A=v[i];
        if(B.x<v[i].x)
            B=v[i];
        else if(B.x==v[i].x&&B.y<v[i].y)
            B=v[i];
    }
    vector<point> up;
    vector<point> down;
    for(int i=1;i<=n;i++)
    {
        double a=aria(A,v[i],B);
        if(a<=0)
            up.push_back(v[i]);
        else
            down.push_back(v[i]);
    }
    down.push_back(A);
    down.push_back(B);
    sort(up.begin(),up.end(),compu);
    sort(down.begin(),down.end(),compd);
    vector<point> hu;
    vector<point> hd;
    for(int i=0;i<up.size();i++)
    {
        while(hu.size()>=2)
        {
            int lg=hu.size();
            if(aria(hu[lg-2],hu[lg-1],up[i])<0)
                hu.pop_back();
            else
                break;
        }
        if(i+1<up.size())
            hu.push_back(up[i]);
    }
    for(int i=0;i<down.size();i++)
    {
        while(hd.size()>=2)
        {
            int lg=hd.size();
            if(aria(hd[lg-2],hd[lg-1],down[i])<0)
                hd.pop_back();
            else
                break;
        }
        if(i+1<down.size())
            hd.push_back(down[i]);
    }
    vector<point> h=hu;
    for(auto i:hd)
        h.push_back(i);
    fout<<h.size()<<'\n';
    for(auto i:h)
        fout<<fixed<<setprecision(12)<<i.x<<' '<<i.y<<'\n';
    return 0;
}