Cod sursa(job #1411094)

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

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

struct Point
{
    double x, y;
};

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;
}

void quickSort(int li, int ls)
{
    int i = li, j = ls;
    int mij = (i + j) / 2;
    Point aux;
    while (i <= j)
    {
        while ((a[i].x < a[mij].x) || ((a[i].x == a[mij].x) && (a[i].y < a[mij].y))) i++;
        while ((a[j].x > a[mij].x) || ((a[j].x == a[mij].x) && (a[j].y > a[mij].y))) j--;
        if (i <= j)
        {
            aux = a[i];
            a[i] = a[j];
            a[j] = aux;
            i++; j--;
        }
    }
    if (li < j) quickSort(li, j);
    if (i < ls) quickSort(i, ls);
}

int main()
{
    int i;
    read();
    quickSort(1, n);
    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;
}