Cod sursa(job #271723)

Utilizator peanutzAndrei Homorodean peanutz Data 5 martie 2009 21:07:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define NMAX 120010
#define EPS 1e-12


typedef struct
{
	double x, y;
} punct;


long n;
punct p[NMAX];
long hull[NMAX], h;
long ex[NMAX], h1;

void read()
{
	long i;
	double x, y;
	scanf("%ld", &n);
	for(i = 1; i <= n; ++i)
	{
		scanf("%lf %lf", &x, &y);
		p[i].x = x;
		p[i].y = y;
	}
}


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 f(double a, double b)
{
	if(a + EPS < b) return -1;
	if(b + EPS < a) return 1;
	return 0;
}

double turn(punct a, punct b, punct c)
{
	int res = f( (a.x-c.x)*(b.y-c.y), (b.x-c.x)*(a.y-c.y) );
	return res;
}

void hull1()
{
	long i;
	h = 0;
	hull[++h] = 1;
	hull[++h] = 2;

	for(i = 3; i <= n; ++i)
	{
		while(h > 1 && turn(p[ hull[h-1] ], p[ hull[h] ], p[i]) > 0)
			--h;
		hull[++h] = i;
	}
}


void hull2()
{
	long i;
	h = 0;
	hull[++h] = 1;
	hull[++h] = 2;

	for(i = 3; i <= n; ++i)
	{
		while(h > 1 && turn(p[ hull[h-1] ], p[ hull[h] ], p[i]) < 0)
			--h;
		hull[++h] = i;
	}
}

int main()
{
	long i, j;

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


	read();


	qsort(p+1, n, sizeof(punct), cmp);
	qsort(p+1, n, sizeof(punct), cmp2);

	//for(i = 1; i <= n; ++i)
	//	printf("%lf %lf\n", p[i].x, p[i].y);

	hull1();

	//for(i = 1; i <= h; ++i)
	//	printf("%lf %lf\n", p[ hull[i] ].x, p[ hull[i] ].y);

	memcpy(ex, hull, sizeof(hull));
	h1 = h;
	hull2();


	printf("%ld\n", h1+h-2);
	for(i = 1; i <= h; ++i)
		printf("%lf %lf\n", p[ hull[i] ].x, p[ hull[i] ].y);

	for(i = h1-1; i >= 2; --i)
		printf("%lf %lf\n", p[ ex[i] ].x, p[ ex[i] ].y);


	return 0;
}