Cod sursa(job #3344637)

Utilizator amunnumeVlad Patrascu amunnume Data 4 martie 2026 12:14:45
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 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.y);
    }
}v[N];
int n,i,j,s[N],sz;
double x,y;
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 main()
{
    fin>>n;
    point mn={2e9,2e9};
    int poz=0;
    for(i=1;i<=n;++i)
    {
        fin>>x>>y;
        v[i]={x,y};
        if(v[i]<mn)
        {
            mn=v[i];
            poz=i;
        }
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    s[1]=1;
    s[2]=2;
    sz=2;
    for(i=3;i<=n;++i)
    {
        while(sz>=2 && sign(v[s[sz-1]],v[s[sz]],v[i])>0)
            --sz;
        s[++sz]=i;
    }
    fout<<fixed;
    fout<<sz<<'\n';
    fout<<setprecision(9)<<v[1].x<<' '<<v[1].y<<'\n';
    for(i=sz;i>=2;--i)
    {
        int j=s[i];
        fout<<setprecision(9)<<v[j].x<<' '<<v[j].y<<'\n';
    }
    return 0;
}