Cod sursa(job #533924)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 februarie 2011 20:28:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 120010

int n, pi, v[nmax], st[nmax];
double x[nmax], y[nmax];

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

double semn(int i1, int i2, int i3)
{
	return 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()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	int i;
	x[0]=y[0]=1<<30;
	for (i=1; i<=n; i++)
	{
		scanf("%lf %lf",&x[i], &y[i]);
		if (x[i]<x[pi] || (x[i]==x[pi] && y[i]<y[pi])) pi=i;
	}
	for (i=1; i<=n; i++)
		if (i!=pi)
			v[++v[0]]=i;
	sort (v+1, v+v[0]+1, cmp);
	int h=1;
	st[1]=pi;
	for (i=1; i<=v[0]; i++)
	{
		while (h>1 && semn(st[h-1], st[h], v[i])>0) h--;
		st[++h]=v[i];
	}
	printf("%d\n",h);
	for (i=h; i>0; i--)
		printf("%lf %lf\n",x[st[i]], y[st[i]]);
}