Cod sursa(job #1610154)

Utilizator PetrutiuPaulPetrutiu Paul Gabriel PetrutiuPaul Data 23 februarie 2016 12:11:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

int n;

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

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

bool slope_compare (const point& a, const point& b)
{
    return (slope (v[1], a, b) < 0);
}

void read ()
{
    f >> n;

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

void sort_the_points ()
{
    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, slope_compare);
}

void convex_hull ()
{
    sort_the_points ();

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

    int last = 2;

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

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

    g << last << '\n';

    g << fixed << setprecision (6);

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

int main()
{
    read ();
    convex_hull ();

    f.close ();
    g.close ();
    return 0;
}