Cod sursa(job #3269985)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 21 ianuarie 2025 17:39:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#define INF 2000000000
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
struct point{
    double x, y;
}s[120005];
int n;
std::vector<point>v;
double det(point a, point b, point c)
{
    a.x-=c.x;
    b.x-=c.x;
    a.y-=c.y;
    b.y-=c.y;
    return a.x*b.y-b.x*a.y;
}
bool cmp(const point &a, const point &b){
    point aux={0, 0};
    double d=det(aux, a, b);
    if(d==0)
        return a.x<b.x;
    return d>0;
}

int main()
{
    int k=0, pmin=0;
    fin>>n;
    v=std::vector<point>(n+5);
    v[0]={INF, INF};
    for(int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y<v[pmin].y || (v[i].y==v[pmin].y && v[i].x<v[pmin].x))
            pmin=i;
    }
    v[0]=v[pmin];
    v[pmin]=v[1];
    v[1]=v[pmin];
    for(int i=1; i<=n; ++i)
    {
        v[i].x-=v[0].x;
        v[i].y-=v[0].y;
    }
    std::sort(v.begin()+2, v.begin()+n+1, cmp);
    s[1]=v[1];
    s[2]=v[2];
    k=2;
    for(int i=3; i<=n; ++i)
    {
        while(k>=2 && det(s[k-1], s[k], v[i])<0)
            --k;
        s[++k]=v[i];
    }
    fout<<k<<'\n';
    for(int i=1; i<=k; ++i)
        fout<<std::fixed<<std::setprecision(12)<<s[i].x+v[0].x<<' '<<s[i].y+v[0].y<<'\n';
    return 0;
}