Cod sursa(job #3349208)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 26 martie 2026 11:04:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define double long double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
    double x, y;
    bool operator < (const elem & other) const
    {
        return (x<other.x || (x==other.x && y<other.y));
    }
};
elem v[200009];
bool viz[200009];
int st[200009], vf=0;
double det (elem a, elem b, elem c)
{
    double x1=a.x, y1=a.y, x2=b.x, y2=b.y, x3=c.x, y3=c.y;
    return x2*y3+x1*y2+y1*x3-x2*y1-x3*y2-y3*x1;
}
signed main ()
{
    int n;
    f >> n;
    for (int i=1; i<=n; i++)
        f >> v[i].x >> v[i].y;
    sort (v+1, v+n+1);
    st[++vf]=1;
    st[++vf]=2;
    viz[2]=1;
    vf=2;
    int i=3;
    int pas=1;
    while (!viz[1])
    {
        while (viz[i])
        {
            if (i==n)
                pas=-1;
            i+=pas;
        }
        while (vf>=2 && det (v[st[vf-1]], v[st[vf]], v[i])<0)
        {
            viz[st[vf]]=0;
            vf--;
        }
        viz[i]=1;
        st[++vf]=i;
    }
    g << vf-1 <<'\n';
    for (int i=2;i<=vf; i++)
        g << fixed << setprecision(8)<< v[st[i]].x << ' ' << v[st[i]].y << '\n';
}