Cod sursa(job #3293744)

Utilizator tudorhTudor Horobeanu tudorh Data 12 aprilie 2025 14:48:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Pct
{
    double x,y;
    bool t;
}p[120000];
bool sortpct(Pct a,Pct b)
{
    return (a.x<b.x || (a.x==b.x && a.y<b.y));
}
double Arie(Pct a,Pct b,Pct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-b.x*a.y-c.x*b.y-a.x*c.y;
}
vector<Pct>s;
int main()
{
    int n;
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>p[i].x>>p[i].y;
    sort(p,p+n,sortpct);
    for(int i=1;i<n-1;i++)
        p[i].t=(Arie(p[0],p[n-1],p[i])>0);
    s.push_back(p[0]);
    for(int i=1;i<n;i++)
    {
        if(p[i].t)
            continue;
        if(s.size()==1)
            s.push_back(p[i]);
        else
        {
            while(s.size()>=2 && Arie(s[s.size()-2],p[i],s[s.size()-1])>0)
                s.pop_back();
            s.push_back(p[i]);
        }
    }
    int size0=s.size();
    p[0].t=1;
    for(int i=n-1;i>=0;i--)
    {
        if(!p[i].t)
            continue;
        if(s.size()==size0)
            s.push_back(p[i]);
        else
        {
            while(s.size()-size0>=1 && Arie(s[s.size()-2],p[i],s[s.size()-1])>0)
                s.pop_back();
            s.push_back(p[i]);
        }
    }
    s.pop_back();
    fout<<s.size()<<'\n';
    fout<<fixed<<setprecision(6);
    for(int i=0;i<s.size();i++)
        fout<<s[i].x<<' '<<s[i].y<<'\n';
    return 0;
}