Cod sursa(job #274814)

Utilizator peanutzAndrei Homorodean peanutz Data 9 martie 2009 23:46:19
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 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 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)
{
	return ( (((punct *)a) -> y) - (((punct *)b) -> y) );
}



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

	long last = 0;
	for(i = 2; i <= n; ++i)
		if(p[i].x != p[i-1].x)
		{
			qsort(p+last+1, i-last+1, sizeof(punct), cmp2);
			last = i;
		}

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