Cod sursa(job #3288694)

Utilizator tudorhTudor Horobeanu tudorh Data 23 martie 2025 17:27:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
    double x,y;
    bool t;
}pct[120001];
bool sortpct(punct a,punct b)
{
    if(a.x<b.x || (a.x==b.x && a.y<b.y))
        return 1;
    return 0;
}
double Arie(punct a,punct b,punct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
punct st[120001];
int main()
{
    int n,sz=0;
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>pct[i].x>>pct[i].y;
    sort(pct,pct+n,sortpct);
    for(int i=1;i<n-1;i++)
    {
        double arie=Arie(pct[0],pct[n-1],pct[i]);
        pct[i].t=(arie>0);
    }
    st[sz++]=pct[0];
    for(int i=1;i<n;i++)
    {
        if(pct[i].t)
            continue;
        if(sz==1)
            st[sz++]=pct[i];
        else
        {
            while(sz>=2 && Arie(st[sz-2],pct[i],st[sz-1])>0)
                sz--;
            st[sz++]=pct[i];
        }
    }
    int sz2=sz;
    pct[0].t=1;
    for(int i=n-1;i>=0;i--)
    {
        if(!pct[i].t)
            continue;
        if(sz2==sz)
            st[sz2++]=pct[i];
        else
        {
            while(sz2-sz>=1 && Arie(st[sz2-2],pct[i],st[sz2-1])>0)
                sz2--;
            st[sz2++]=pct[i];
        }
    }
    sz2--;
    fout<<fixed<<setprecision(6);
    fout<<sz2<<'\n';
    for(int i=0;i<sz2;i++)
        fout<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}