Cod sursa(job #274757)

Utilizator peanutzAndrei Homorodean peanutz Data 9 martie 2009 22:56:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

using namespace std;

#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(punct a, punct b)
{
	if(a.x < b.x)
		return 1;
	if(a.x == b.x && a.y < b.y)
		return 1;
	return 0;
}

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);
	sort(p+1, p+n+1, cmp);

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