Cod sursa(job #431447)

Utilizator NemultumituMatei Ionita Nemultumitu Data 31 martie 2010 23:55:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,h,st[120050],sol[120050];
struct punct
{
	double x,y;
};
punct v[120050];

void citire()
{
	freopen ("infasuratoare.in","r",stdin);
	freopen ("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%lf%lf",&v[i].x,&v[i].y);
}

bool comp (const punct &a,const punct &b)
{
	if (a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}

double dreapta (int i,int j)
{
	return v[st[i-2]].x*v[st[i-1]].y+v[st[i-1]].x*v[j].y+v[j].x*v[st[i-2]].y-v[j].x*v[st[i-1]].y-v[st[i-1]].x*v[st[i-2]].y-v[st[i-2]].x*v[j].y;
}

int main()
{
	citire();
	sort(v+1,v+1+n,comp);
	st[1]=1;
	st[2]=2;
	int i=3,j=3;
	do
	{
		while (dreapta(i,j)<0&&i>2)
			st[i--]=0;
		st[i++]=j++;
	}
	while (j<=n);
	for (int i=1;st[i];++i)
		sol[++h]=st[i];
	memset(st,0,sizeof(st));
	
	st[1]=1;
	st[2]=2;
	i=3;
	j=3;
	do
	{
		while (dreapta(i,j)>0&&i>2)
			st[i--]=0;
		st[i++]=j++;
	}
	while (j<=n);
	i-=2;
	for (;i>1;--i)
		sol[++h]=st[i];
	printf("%d\n",h);
	for (int i=1;i<=h;++i)
		printf("%lf %lf\n",v[sol[i]].x,v[sol[i]].y);
	return 0;
}