Cod sursa(job #327558)

Utilizator TyberFMI Dogan Adrian Ioan Lucian Tyber Data 29 iunie 2009 12:57:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<algorithm>
#define nmax 120000
#define inf 1000000000
using namespace std;
double cmpf(int,int);
double semn(int,int,int);
int n,pi,ind[nmax],st[nmax];
double x[nmax],y[nmax];
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	x[0]=y[0]=inf;
	int p_i=0,i;
	for(i=1;i<=n;i++)
	{
		scanf("%lf %lf",&x[i],&y[i]);
		if(x[i]<x[p_i]||(x[i]==x[p_i]&&y[i]<y[p_i]))
			p_i=i;
	}
	pi=p_i;
	for(i=1;i<=n;i++)
	{
		if(i==p_i)
			continue;
		ind[++ind[0]]=i;
	}
	sort(ind+1,ind+ind[0]+1,cmpf);
	st[0]=1;
	st[1]=p_i;
	for(i=1;i<=ind[0];i++)
	{
		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]]=p_i;
	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;
}
double cmpf(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];
}