Cod sursa(job #2576488)

Utilizator mihailrazMihail Turcan mihailraz Data 6 martie 2020 19:51:23
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const int nmax=12e4;
int n, vf=2;
int hull[nmax+5];

struct punct
{
    double x, y;
} P[nmax+5];

int cmp(punct a, punct b)
{
    if(a.x<b.x)
        return 1;
    if(a.x==b.x)
        return a.y<b.y;
    return 0;
}

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

int main()
{
    fi>>n;
    for(int i=1; i<=n; i++)
        fi>>P[i].x>>P[i].y;

    sort(P+1, P+n+1, cmp);

    hull[1]=1;
    hull[2]=2;
    for(int i=3; i<=n; i++)
    {
        while(vf>=2 && det(P[hull[vf-1]], P[hull[vf]], P[i])<0)
            vf--;
        hull[++vf]=i;
    }
    for(int i=n-1; i>=1; i--)
    {
        while(vf>=2 && det(P[hull[vf-1]], P[hull[vf]], P[i])<0)
            vf--;
        hull[++vf]=i;
    }

    fo<<vf-1<<"\n";
    for(int i=1; i<vf; i++)
        fo<<fixed<<setprecision(12)<<P[hull[i]].x<<" "<<P[hull[i]].y<<"\n";

    fi.close();
    fo.close();
    return 0;
}