Cod sursa(job #3293884)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 12 aprilie 2025 21:18:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
    double x, y;
}v[120009];
int st[120009];
bool viz[200009];
int top;
bool comp (const elem & x, const elem & y)
{
    return ((x.x<y.x) || (x.x==y.x && x.y<y.y));
}
double panta (elem a, elem b, elem c)
{
    return (c.y-a.y)*(b.x-a.x)-(b.y-a.y)*(c.x-a.x);
}
int 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, comp);
    st[1]=1, st[2]=2, viz[2]=1, top=2;
    int pas=1;
    int i=3;
    while (!viz[1])
    {
        while (viz[i])
        {
            if (i==n) pas=-1;
            i+=pas;
        }
        while (top >=2 && panta (v[st[top-1]], v[st[top]], v[i])<0)
        {
            viz[st[top]]=0;
            top--;
        }
        viz[i]=1;
        st[++top]=i;
    }
    g << top-1 << '\n';
    for (int i=2; i<=top; i++)
        g << fixed << setprecision(8) << v[st[i]].x << ' ' << fixed << setprecision(8) << v[st[i]].y << '\n';
}