Cod sursa(job #631662)

Utilizator geniucosOncescu Costin geniucos Data 9 noiembrie 2011 14:00:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,i,l,w;
int s[120002],ap[120002];
struct vec
{
	float x;
	float y;
	int p;
};
bool cmp(vec a,vec b)
{
	if(a.y==b.y)
	{
		if(a.x<b.x) return 1;
		else return 0;
	}
	else return a.y<b.y;
}
int det(float x1,float y1,float x2,float y2,float x3,float y3)
{
	float s1;
	s1=float((x1*y2)+(x2*y3)+(x3*y1)-(y2*x3)-(y3*x1)-(y1*x2));
	if(s1>=0) return 0;
	return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
vec v[120002];
for(i=1;i<=n;i++)
{
	scanf("%f",&v[i].x);
	scanf("%f",&v[i].y);
}
for(i=1;i<=n;i++)
	v[i].p=i;
sort(v+1,v+n+1,cmp);
l=1;
s[1]=v[1].p;
for(i=2;i<=n;i++)
{
	if(l==1)
	{
		l++;
		s[l]=v[i].p;
	}
	else
	{
		w=l-1;
		while(det(v[s[w]].x,v[s[w]].y,v[s[w+1]].x,v[s[w+1]].y,v[i].x,v[i].y)==0&&w!=0) w--;
		w=w+2;
		l=w;
		s[w]=v[i].p;
	}
}
for(i=1;i<=l;i++)
	ap[s[i]]=1;
for(i=1;i<=n;i++)
	if(ap[i]==0)
	{
		if(l==1)
		{
			l++;
			s[l]=v[i].p;
		}
		else
		{
			w=l-1;
			while(det(v[s[w]].x,v[s[w]].y,v[s[w+1]].x,v[s[w+1]].y,v[i].x,v[i].y)==0&&w!=0) w--;
			w=w+2;
			l=w;
			s[w]=v[i].p;
		}
	}
for(i=1;i<=l;i++)
{
	printf("%.6f ",v[s[i]].x);
	printf("%.6f\n",v[s[i]].y);
}
return 0;
}