Cod sursa(job #411962)

Utilizator laserbeamBalan Catalin laserbeam Data 5 martie 2010 11:43:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
// Catalin Balan
// Fri Mar  5 10:00:26 EET 2010
// Infoarena - Infasuratoare convexa 

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define	NMAX 120003

#define FIN "infasuratoare.in"
#define FOUT "infasuratoare.out"

double x[NMAX],y[NMAX];
int ind[NMAX], n, luate[NMAX];


// p1 - punctu nou, p2 - ultimul punct adaugat, p3 - penultimul punct adaugat
// semn < 0 - intoarcere spre stanga; semn > 0 spre dreapta
long double semn(int p1, int p2, int p3) 
{
	return (long double)(x[p1] - x[p3]) * (y[p2] - y[p3]) - (long double)(y[p1] - y[p3]) * (x[p2] - x[p3]);
}

bool cmp(int a, int b)
{
	if (x[a] == x[ind[1]]) return false;
	if (x[b] == x[ind[1]]) return true;
	return ( (long double)(x[b] - x[ind[1]]) * (y[a] - y[ind[1]]) < 
			 (long double)(x[a] - x[ind[1]]) * (y[b] - y[ind[1]]) );
}

int main(int argv, char ** argc)
{
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	int p;
	scanf("%d\n", &n);
	double minx, miny;
	minx = miny = 1000000003;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%lf %lf", &x[i], &y[i]);
		ind[i] = i;
		if ( x[i] < minx || (x[i] == minx && y[i] < miny))
		{
			miny = y[i];
			minx = x[i];
			p = i;
		}
	}
	ind[p] = 1;
	ind[1] = p;

	sort (ind+2, ind+n+1, cmp);

//	for (int i = 1; i <= n; ++i) fprintf(stderr, "%lf %lf\n", x[ind[i]], y[ind[i]]);
	
//	fprintf(stderr, "\n\n");

	luate[1] = ind[1];
	luate[2] = ind[2];
	p = 2;
	for (int i = 3; i <= n; ++i)
	{
//		fprintf(stderr, "%d %d %llf\n", i, p, semn( ind[i], luate[p], luate[p-1] ) );
		while ( semn( ind[i], luate[p], luate[p-1] )>0 ) 
		{
			--p;
//			fprintf(stderr, "%d %d %llf\n", i, p, semn( ind[i], luate[p], luate[p-1] ) );
		}
		luate[++p] = ind[i];
	}
	printf("%d\n", p);
	for (int i = 1; i <= p; ++i) printf("%lf %lf\n", x[luate[i]], y[luate[i]]);

	return EXIT_SUCCESS;
}