Cod sursa(job #1610149)

Utilizator PetrutiuPaulPetrutiu Paul Gabriel PetrutiuPaul Data 23 februarie 2016 12:08:38
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct point
{
    double x;
    double y;
} v[120005], stiva[120005];

int n;

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

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

void convex_hull()
{
    int poz = 1;

    for (int i = 2; i <= n; i ++)
        if (v[i].y < v[poz].y || (v[i].y == v[poz].y && v[i].x < v[poz].x))
            poz = i;

    point aux;

    aux = v[1];
    v[1] = v[poz];
    v[poz] = aux;

    sort(v+2,v+n+1,cmp);

    stiva[1]=v[1];
    stiva[2]=v[2];

    int top=2;

    for(int i=3;i<=n;i++)
    {
        while(det(stiva[top-1],stiva[top],v[i])>0 && top>=2)
            --top;

        stiva[++top]=v[i];
    }

    fout<<top<<'\n';

    fout<<fixed<<setprecision(6);

    for (int i = 1; i <= top; i ++)
        fout<<stiva[i].x<<" "<<stiva[i].y<<'\n';
}

int main()
{
    fin>>n;

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

    convex_hull();

    return 0;
}