Cod sursa(job #294858)

Utilizator cotofanaCotofana Cristian cotofana Data 2 aprilie 2009 20:07:06
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#define dim 120100

using namespace std;

int n, s[dim], k;
double x[dim], y[dim];

long double semn(int n1, int n2, int n3)
{
	return (long double)x[n1]*y[n2]+x[n2]*y[n3]+x[n3]*y[n1]-y[n1]*x[n2]-y[n2]*x[n3]-y[n3]*x[n1];
}

void graham()
{
	int i;
	s[0]=1;
	s[1]=2;
	s[2]=3;
	k=2;
	for (i=4; i<=n; i++)
	{
		while (semn(s[k-1], s[k], i)<=0) 
			k--;
		s[++k]=i;
	}
}

void swap(double &a, double &b)
{ 
	double t=a;
	a=b;
	b=t;
}

int comp(int n1, int n2)
{
	double a, b;
	a=(y[n1]-y[1])*(x[n2]-x[1]);
	b=(y[n2]-y[1])*(x[n1]-x[1]);
	if (a<b) return -1;
	if (a==b) return 0;
	return 1;
}

void sort(int lo, int hi)
{
	int i=lo, j=hi, m=i+(j-i)/2;
	do
	{
		while (comp(i, m)<0) i++;
		while (comp(m, j)<0) j--;
		if (i<=j)
		{
			swap(x[i], x[j]);
			swap(y[i], y[j]);
			i++, j--;
		}
	} while(i<=j);
	if (lo<j) sort(lo, j);
	if (i<hi) sort(i, hi);
}

int main()
{
	int i, in;
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d\n", &n);
	for (i=1; i<=n; i++) scanf("%lf %lf\n", &x[i], &y[i]);
	in=1;
	for (i=2; i<=n; i++)
		if ((y[i]<y[in]) || (y[i]==y[in] && x[i]<x[in])) in=i;
	if (in!=1)
	{
		swap(x[1], x[in]);
		swap(y[1], y[in]);
	}
	sort(2, n);
	graham();
	printf("%d\n", k+1);
	for (i=0; i<=k; i++) printf("%lf %lf\n", x[s[i]], y[s[i]]);
	return 0;
}