Cod sursa(job #271937)

Utilizator peanutzAndrei Homorodean peanutz Data 6 martie 2009 09:08:32
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define NMAX 120010


typedef struct
{
	double x, y;
} punct;


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

void swap(int i, int j)
{
	punct aux;
	aux = p[i];
	p[i] = p[j];
	p[j] = aux;
}

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) );
}

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

void convexhull()
{
	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);

	convexhull();

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

	for(i = 1; i <= n/2; ++i)
		swap(i, n-i+1);

	convexhull();

	printf("%ld\n", h1+h-2);

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

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

	return 0;
}