Cod sursa(job #2809943)

Utilizator RTG123Razvan Diaconescu RTG123 Data 27 noiembrie 2021 23:03:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,viz[120001],st[120001],nr;
double a,b;
struct imp
{
    double a,b;
};
imp afis[120001];
bool cmp(imp x,imp y)
{
    if (x.a>y.a)
        return 0;
    else if (x.a==y.a)
    {
        if (x.b>y.b)
            return 0;
        else return 1;
    }
    else return 1;
}
imp v[120001];
double dir (imp x,imp y,imp z)
{
    return (y.a-x.a)*(z.b-x.b)-(y.b-x.b)*(z.a-x.a);
}
int main()
{
    f>>n;
    for (int i=1; i<=n; i++)
    {
        f>>v[i].a>>v[i].b;
        //cout<<v[i].a<<' '<<v[i].b<<'\n';
    }
    sort(v+1,v+1+n,cmp);
    for (int i=1; i<=n; i++)
    {
       // cout<<v[i].a<<' '<<v[i].b<<'\n';
        //cout<<v[i].a<<' '<<v[i].b<<'\n';
    }
    st[1]=1;
    st[2]=2;
    viz[2]=1;
    nr=2;
    for (int i=1,p=1; i>0; i+=(p=(i==n ? -p : p)))
    {
        if (viz[i]==0)
        {
            while (nr>=2 && dir(v[st[nr-1]],v[st[nr]],v[i])<=0)
            {
                //cout<<i<<' '<<nr<<'\n';
                viz[st[nr]]=0;
                nr--;
            }
            nr++;
            st[nr]=i;
            viz[i]=1;
        }
    }
    g<<setprecision(6)<<fixed;
    g<<nr-1<<'\n';
    for (int i=1; i<nr; i++)
    {
        g<<v[st[i]].a<<' '<<v[st[i]].b<<'\n';
    }
    return 0;
}