Cod sursa(job #488106)

Utilizator acelasi7Tudor Maxim acelasi7 Data 27 septembrie 2010 17:53:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#include<stdio.h>
using namespace std;

#define maxn 120001
#define inf 1000000000

double x[maxn],y[maxn];
long double v[maxn];
int pi,ind[maxn],st[maxn],n;
bool comf(int i,int j) //compar unghiul phi dintre 2 puncte cu orizontala...cu tangenta...
{
	return (double)(x[i]-x[pi])*(y[j]-y[pi])<(double)(x[j]-x[pi])*(y[i]-y[pi]);
}
long double semn(int i,int j,int k)
{
	return (x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-y[i]*x[j]-y[j]*x[k]-y[k]*x[i]);
}
int main()
{
	int pctinitial=0,i;
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d\n",&n);
	x[pctinitial]=y[pctinitial]=inf;
	for(i=1;i<=n;i++)
	{
		scanf("%lf %lf\n",&x[i],&y[i]);
		if(x[i]<x[pctinitial]||(x[i]==x[pctinitial]&&y[i]<y[pctinitial]))
			pctinitial=i;
	}
	pi=pctinitial;
	for(i=1;i<=n;i++)
		if(i!=pi)
			ind[++ind[0]]=i;
	sort(ind+1,ind+ind[0]+1,comf);
	st[0]=1;
	st[1]=pctinitial;
	for(i=1;i<n;i++)
	{
		if(ind[i]==pctinitial) continue ;
		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]]=pi;
	reverse(st+1,st+st[0]+1);
	printf("%d\n",st[0]-1);
	for(i=1;i<st[0];i++)
	{
		printf("%lf %lf\n",x[st[i]],y[st[i]]);
	}
	return 0;
}