Cod sursa(job #273266)

Utilizator MarquiseMarquise Marquise Data 8 martie 2009 13:25:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include <stdio.h>
#include <math.h>

#define NMAX 120002
#define eps 0.000000000001

int N, st[NMAX];

struct POINT
{
	double x, y;
};

POINT a[NMAX];

double FABS( double x)
{
	return x < 0.0 ? -x : x;
}

double dist(POINT A, POINT B)
{
	return sqrt( ( A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) );
}

int same_point(POINT A, POINT B)
{
	return ( FABS( A.x - B.x) < eps && FABS(A.y - B.y) < eps );
}

int ccw(POINT A, POINT B, POINT C)
{
	double p;

	p = (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * ( C.x - B.x);

	if ( FABS(p) < eps )
		return 0;

	if ( p > eps)
		return 1;

	return -1;
}

int comp(POINT A, POINT B, POINT C)
{
	int c;

	c = ccw(A, B, C);

	if ( c == 1)
		return 1;
	else
		if ( c == - 1)
			return 0;
		else
		{
			if ( dist(A, C) - dist(A, B) >= eps)
				return 1;
			else
				return 0;
		}
}

int partitie(int st, int dr)
{
	int i, j;
	POINT aux, pivot;

	i = st - 1;
	j = dr + 1;
	pivot = a[(st + dr) / 2];

	while (1)
	{
		do { ++i; } while ( comp(a[0], a[i], pivot) == 1 && !same_point(a[i], pivot) );
		do { --j; } while ( comp(a[0], a[j], pivot) == 0 && !same_point(a[j], pivot) );

		if ( i < j)
		{
			aux = a[i];
			a[i] = a[j];
			a[j] = aux;
		}
		else
			return j;
	}
}

void sort(int st, int dr)
{
	int m;
	if ( st < dr)
	{
		m = partitie(st, dr);
		sort( st, m);
		sort( m + 1, dr);
	}
}

void solve()
{
	int top, i;

	top = 1;
	i = 2;
	st[0] = 0;
	st[1] = 1;
	a[N] = a[0];

	while ( i <= N)
	{
		if ( ccw( a[st[top - 1]], a[st[top]], a[i]) == 1)
		{
			st[++top] = i;
			i++;
		}
		else
			top--;
	}

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

int main()
{
	int i, poz;
	POINT min, aux;

	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

	scanf("%d", &N);

	for ( i = 0; i < N; i++)
		scanf("%lf %lf", &a[i].x, &a[i].y);

	min = a[0];
	poz = 0;

	for ( i = 1; i < N; i++)
		if ( a[i].y < min.y || ( FABS(a[i].y - min.y) < eps && a[i].x < min.x) )
		{
			min = a[i];
			poz = i;
		}

	aux = a[0];
	a[0] = a[poz];
	a[poz] = aux;
	
	sort(1, N - 1);
	solve();
	return 0;
}