Cod sursa(job #3348763)

Utilizator amunnumeVlad Patrascu amunnume Data 23 martie 2026 21:19:53
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int N=12e4+5;
struct point
{
    double x,y;
    bool operator<(const point& e) const
    {
        return (y<e.y)||(y==e.y && x<e.x);
    }
}v[N];
int sign(point a,point b,point c)
{
    double r=a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
    if(!r) return 0;
    return (r<0)?-1:1;
}
bool cmp(point a,point b)
{
    return sign(v[1],a,b)<0;
}
int n,i,j,s[N],ss;
double x,y;
int main()
{
    ///Sorting is negative
    ///Convex Hull is pozitive
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>x>>y;
        v[i]={x,y};
    }
    point mn=v[1];
    int poz=1;
    for(i=2;i<=n;++i)
    {
        if(v[i]<mn)
        {
            mn=v[i];
            poz=i;
        }
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    ///1 is eternal
    s[1]=1; s[2]=2;
    ss=2;
    for(i=3;i<=n;++i)
    {
        //cout<<v[i].y<<'\n';
        while(ss>=2 && sign(v[s[ss-1]],v[s[ss]],v[i])>0)
            --ss;
        s[++ss]=i;
    }
    fout<<fixed;
    fout<<ss<<'\n';
    fout<<setprecision(6)<<v[1].x<<' '<<v[1].y<<'\n';
    for(int i=ss;i>=2;--i)
       fout<<setprecision(6)<<v[s[i]].x<<' '<<v[s[i]].y<<'\n';
    return 0;
}