Cod sursa(job #780347)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 20 august 2012 12:57:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cassert>
#include <cstdio>

#include <algorithm>

using namespace std;

struct puncte {
    double x;
    double y;
};

const int N = 120005;
const int INF = 0x3f3f3f3f;

int n, dim;
puncte p[N], stiva[N];

void cauta_stanga()
{
    int poz = n + 1;
    p[poz].x = p[poz].y = INF;

    for (int i = 1; i <= n; ++i)
        if (p[i].x < p[poz].x)
            poz = i;
        else if (p[i].x == p[poz].x && p[i].y < p[poz].y)
            poz = i;

    swap(p[1], p[poz]);
}

double tg(puncte a, puncte b)
{
    return (double)(a.y - b.y) / (a.x - b.x);
}

int cmp(puncte a, puncte b)
{
    return tg(a, p[1]) < tg(b, p[1]);
}

double det(puncte a, puncte b, puncte c)
{
    return (double)a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}

void infasuratoare()
{
    sort(p + 2, p + n + 1, cmp);

    dim = 1;
    stiva[1] = p[1];

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

int main()
{
    assert(freopen("infasuratoare.in", "r", stdin));
    assert(freopen("infasuratoare.out", "w", stdout));

    assert(scanf("%d", &n) == 1);
    for (int i = 1; i <= n; ++i)
        assert(scanf("%lf %lf", &p[i].x, &p[i].y) == 2);

    cauta_stanga();
    infasuratoare();
    
    printf("%d\n", dim);
    for (int i = 1; i <= dim; ++i)
        printf("%.12lf %.12lf\n", stiva[i].x, stiva[i].y);
}