Cod sursa(job #3277832)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 17 februarie 2025 14:44:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
    double x, y;
};
elem v[120009];
bool comp (elem x, elem y)
{
    if (x.x<y.x) return 1;
    if (x.x==y.x && x.y<y.y) return 1;
    return 0;
}
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 st[120009], viz[120009], top, n;
void solve ()
{
    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--;
        }
        st[++top]=i;
        viz[i]=1;
    }
}
int main ()
{
    f >> n;
    for (int i=1; i<=n; i++)
        f >> v[i].x >> v[i].y;
    sort (v+1, v+n+1, comp);
    solve();
    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';
}