Cod sursa(job #271941)

Utilizator peanutzAndrei Homorodean peanutz Data 6 martie 2009 09:22:26
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <stdlib.h>
#include <stdio.h>
//#include <algorithm>

//using namespace std;

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

typedef struct
{
	double x, y;
} punct;

int N, H;
punct v[NMAX], P[NMAX];

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


int cmp(const void *a, const void *b)
{
	return ( (((punct *)a) -> x) - (((punct *)b) -> x) );
}

int cmp2(const void *a, const void *b)
{
	if(   ( (((punct *)a) -> x) == (((punct *)b) -> x) ) )
		return ( (((punct *)a) -> y) - (((punct *)b) -> y) );
	return ( (((punct *)a) -> x) - (((punct *)b) -> x) );
}

/*
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(punct a, punct b, punct 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 st[NMAX], uz[NMAX];
void ConvexHull()
{
    int i, pas = +1, k;

    //sort(v+1, v+N+1, cmp_PDD);
     qsort(v+1, N, sizeof(punct), cmp);
     qsort(v+1, N, sizeof(punct), cmp2);

    uz[2] = 1; st[1] = 1; st[2] = 2; k = 2; i = 3;
    while (!uz[1])
    {
	while (uz[i])
	{
	    if (i == N)
		pas = -1;
	    i += pas;
	}
	while (k >= 2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1)
	    uz[st[k--]] = 0;
	st[++k] = i; uz[i] = 1;
    }
    H = k-1;
    for (i = 1; i <= H; ++i)
	P[i] = v[st[i]];
    P[H+1] = P[1];
}


int main()
{
    int i;
    double x, y;
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
    {
	scanf("%lf %lf", &x, &y);
	v[i].x = x;
	v[i].y = y;
    }
    ConvexHull();
    printf("%d\n", H);
    for (i = 1; i <= H; ++i)
	printf("%.6lf %.6lf\n", P[i].x, P[i].y);
    
    return 0;
}