Cod sursa(job #1410908)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 31 martie 2015 12:40:41
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 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, i, size, s[nmax], viz[nmax];

Point a[nmax];

void read()
{
    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 pos)
{
    while ((size >= 2) && (cross_product(a[s[size - 1]], a[s[size]], a[pos]) < eps))
    {
        viz[s[size]] = 0;
        size--;
    }
    size++;
    s[size] = pos;
    viz[pos] = 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()
{
    read();
    quickSort(1, n);
    s[1] = 1;
    s[2] = 2;
    size = 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 << size - 1 << '\n';
    g << fixed << setprecision(12);
    for (i = 1; i < size; i++) g << a[s[i]].x << " " << a[s[i]].y << "\n";
    return 0;
}