Cod sursa(job #2857398)

Utilizator norryna07Alexandru Norina norryna07 Data 25 februarie 2022 15:28:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#define zero 1e-12
#define N 120005
using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct punct
{
    double x, y;
} a[N];
int n;
bitset <N> viz;

void citire()
{
    fin>>n;
    for (int i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
    fin.close();
}

inline bool cmp(punct a, punct b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}

double aria(punct o, punct a, punct b)
{
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}

void convex_hull()
{
    ///sortam elementele dupa x si dupa y
    sort(a+1, a+n+1, cmp);
    int st[N];
    int top; ///stiva
    ///adaugam in stiva prima muchie intre pct 1 si 2
    st[1]=1; st[2]=2; top=2;
    viz[2]=1;
    for (int i=1, p=1; i>0; i+=(p=(i==n ? -p:p)))
        if (!viz[i])
        {
            while (top>=2 && aria(a[st[top-1]], a[st[top]], a[i])<zero)
                viz[st[top--]]=0;
            st[++top]=i;
            viz[i]=1;
        }
    fout<<top-1<<'\n';
    fout<<setprecision(6)<<fixed;
    for (int i=1; i<top; ++i)
        fout<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
}

int main()
{
    citire();
    convex_hull();
    return 0;
}