Cod sursa(job #1411152)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 31 martie 2015 14:44:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>
using namespace std;

fstream f("infasuratoare.in", ios::in);
fstream g("infasuratoare.out", ios::out);

struct Point
{
    double x, y;
    bool operator < (const Point &p) const
    {
        if (p.x > x) return true;
        if (p.x < x) return false;
        if (p.y > y) return true;
        return false;
    }
};

const int nmax = 120010;
const double eps = 1e-12;

int n, head, s[nmax], viz[nmax];

Point a[nmax];

void read()
{
    int i;
    f >> n;
    for (i = 1; i <= n; i++)
    {
        f >> a[i].x >> a[i].y;
    }
}

double cross_product(Point A, Point B, Point C)
{
    return (C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x);
}

void convex_hull(int poz)
{
    while ((head >= 2) && (cross_product(a[s[head - 1]], a[s[head]], a[poz]) < eps))
    {
        viz[s[head]] = 0;
        head--;
    }
    head++;
    s[head] = poz;
    viz[poz] = 1;
}

int main()
{
    int i;
    read();
    sort(a + 1, a + n + 1);
    s[1] = 1;
    s[2] = 2;
    head = 2;
    viz[2] = 1;
    for (i = 3; i < n; i++) if (!viz[i]) convex_hull(i);
    for (i = n; i >= 1; i--) if (!viz[i]) convex_hull(i);
    g << head - 1 << '\n';
    g << fixed << setprecision(12);
    for (i = 1; i < head; i++) g << a[s[i]].x << " " << a[s[i]].y << "\n";
    return 0;
}