Cod sursa(job #641691)

Utilizator sebii_cSebastian Claici sebii_c Data 29 noiembrie 2011 02:18:28
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

const int nmax = 120002;
const int inf = (2e9);

int n,pi,punct_init,i,st[nmax],ind[nmax];
double x[nmax],y[nmax];

bool cmp(int i,int j)
{
	return (double)(x[i] - x[pi]) * (y[j] - y[pi]) < (double)(x[j] - x[pi]) * (y[i] - y[pi]);
}

long double semn(int i1,int i2,int i3)
{
	return (long double) x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1];
}

int main()
{
	ifstream f("infasuratoare.in");
	freopen("infasuratoare.out", "w", stdout);

	f>>n;
	x[0]=y[0]=inf;
	punct_init=0;
	for (i=1; i<=n; ++i)
	{
		f>>x[i]>>y[i];
		if (x[i]<x[punct_init] || (x[i]==x[punct_init] && y[i]<y[punct_init]))
			punct_init=i;
	}
	pi=punct_init;

	for (i=1; i<=n; ++i)
		if (i!=punct_init)
			ind[++ind[0]] = i;
	sort(ind+1, ind+ind[0]+1, cmp);

	st[++st[0]] = punct_init;
	for (i=1; i<=ind[0]; ++i)
	{
		if (ind[i]!=punct_init)
			while (st[0]>=2 && semn(st[st[0]-1],st[st[0]],ind[i]) > 0)
				--st[0];
		st[++st[0]] = ind[i];
	}
	st[++st[0]] = punct_init;

	printf("%d\n", st[0]-1);
	reverse(st + 1, st + st[0] + 1);
	for (i=1; i<st[0]; ++i)
		printf("%lf %lf\n", x[st[i]], y[st[i]]);

	return 0;
}