Cod sursa(job #2878742)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 27 martie 2022 15:20:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

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

struct punct
{
    double x, y;
} v[120005], st[120005], pct;

int n, pos, vf, i;

bool cmp(punct a, punct b);
double det(punct a, punct b, punct c);

int main()
{
    fin>>n;
    pct.x=1e9;
    pct.y=1e9;
    for(i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y<pct.y)
        {
            pct=v[i];
            pos=i;
        }
        else if(v[i].y==pct.y && v[i].x<pct.x)
        {
           pct=v[i];
           pos=i;
        }
    }
    swap(v[1], v[pos]);
    sort(v+2, v+n+1, cmp);
    st[vf++]=v[1];
    st[vf]=v[2];
    for(i=3; i<=n; i++)
    {
        while(vf>=1 && det(st[vf-1], st[vf], v[i])>0)
            vf--;
        st[++vf]=v[i];
    }
    fout<<vf+1<<'\n';
    while(vf>=0)
    {
        fout<<setprecision(9)<<fixed<<st[vf].x<<' '<<st[vf].y<<'\n';
        vf--;
    }
}

bool cmp(punct a,punct b)
{
    return(det(v[1], a, b)<0);
}

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