Cod sursa(job #999195)

Utilizator gbi250Gabriela Moldovan gbi250 Data 19 septembrie 2013 17:41:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#define x first
#define y second
using namespace std;

const int eps = 1e-12;
typedef pair <double, double> point;

int n, i, top, st[120005];
bool visited[120005];

point v[120005];

double cross_product(point prev, point curr, point next)
{
    return (curr.x - prev.x) * (next.y - prev.y) - (next.x - prev.x) * (curr.y - prev.y);
}

inline void convex_hull()
{
    sort(v+1, v+n+1);

    st[++top] = 1;

    for (int i = 2, p = 1; i > 0; i += (p = (i == n ? -p : p)))
        if(!visited[i])
        {
            while( cross_product( v[ st[top-1] ], v[ st[top] ], v[i]) <= eps && top >= 2)
                visited[ st[top--] ] = 0;

            visited[ st[++top]=i ] = 1;
        }
}

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

    convex_hull();

    printf("%d\n", top-1);

    for(i=1; i<top; ++i)
        printf("%6lf %6lf\n", v[ st[i] ].x, v[ st[i] ].y);
    return 0;
}