Cod sursa(job #600038)

Utilizator cont_de_testeCont Teste cont_de_teste Data 30 iunie 2011 13:33:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <algorithm>
#include <deque>
using namespace std;

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

#define INF 1000000000
#define EPS 1e-12
#define PDD pair<double, double>
#define x first
#define y second

int N, H;
PDD v[120005], P[120005];

inline int cmp(double a, double b)
{
    if (a + EPS < b) return -1;
    if (b + EPS < a) return +1;
    return 0;
}

int cmp_PDD(const PDD &a, const PDD& b)
{
    int r = cmp(a.x, b.x);
    if (r != 0) return r == -1;
    return cmp(a.y, b.y) == -1;
}

int semn(PDD a, PDD b, PDD c)
{
    double A = a.y-b.y, B = b.x-a.x, C = a.x*b.y - b.x*a.y;
    return cmp(A * c.x + B * c.y + C, 0);
}

int uz[120005];
deque <int> st;
void ConvexHull()
{
    int i, pas = +1, k;

    sort(v+1, v+N+1, cmp_PDD);
st.push_back (1), st.push_back (2); // st[1] = 1; st[2] = 2;
    uz[2] = 1; k = 2; i = 3;
    while (!uz[1])
    {
        for (; uz[i] ; i += pas = (i == N ? -1 : pas)) ;
        while (st.size () >= 2 && semn(v[*(st.end ()-2)], v[st.back()], v[i]) == -1)
            uz[st.back ()] = 0, st.pop_back ();//uz[st[k--]] = 0;
        st.push_back (i),  uz[i] = 1; // st[++k] = i;
    }
    H = st.size ()-1;
    for (i = 1; i <= H; ++i)
        P[i] = v[st[i - 1]];
    P[H + 1] = P[1];
}

int main()
{
    int i;
freopen ("infasuratoare.in", "r", stdin);
 scanf ("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf ("%lf %lf", &v[i].x,&v[i].y);

    ConvexHull();

    freopen ("infasuratoare.out", "w", stdout);
    printf("%d\n", H);
    for (i = 1; i <= H; ++i)
        printf("%.6lf %.6lf\n", P[i].x, P[i].y);

    return 0;
}