Cod sursa(job #696093)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 28 februarie 2012 16:45:11
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#define dist (sqrt(a.x*a.x+a.y*a.y))
#define pi 3.14159265
using namespace std;
struct punct 
{
	float x,y;
}v[120000],aux;
int m,n,i,j,k,q[120000];
bool ok;
inline float panta(float x1, float y1, float x2, float y2)
{
	if(x2-x1<0.0001) return 2000000000;
	return((y2-y1)/(x2-x1));
}
inline float mm(float k)
{
	return (k>0? k : -k);
}
bool cmp(punct x , punct y)
{
	return (panta ( v[0].x , v[0].y , x.x , x.y ) < panta ( v[0].x , v[0].y , y.x , y.y ) );
}
inline float unghi(punct a, punct o)
{
	a.x-=o.x;a.y-=o.y;
	float qq;
	qq=0;
	if(a.x>0&&a.y>0) qq= ( asin(a.y/dist));
	if(a.x<0&&a.y>0) qq= (pi/2 + asin(-a.x/dist));
	if(a.x<0&&a.y<0) qq= (pi + asin(-a.y/dist));
	if(a.x>0&&a.y<0) qq= (3*pi/2 + asin(a.x/dist));
	if(mm(a.x)<0.001)
	{
		if(a.y>0) qq=pi/2;
		if(a.y<0) qq=3*pi/2;
	}
	if(mm(a.y)<0.001)
	{
		if(a.x>0) qq=0;
		if(a.x<0) qq=pi;
	}
	return qq;
}
inline bool check(punct a, punct o, punct b)
{
	float h1,h2,h;
	h1=unghi(a,o);
	h2=unghi(b,o);
	h=h1-h2;
	if(h<0)h+=2*pi;
	if(h<3.14159265) return 1;
	return 0;
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	j=0;
	for(i=0;i<n;i++)
	{
		scanf("%f%f",&v[i].x,&v[i].y);
		if(v[i].x<v[j].x || ( v[i].x==v[j].x && v[i].y<v[j].y )) j=i;
	}
	aux=v[0];v[0]=v[j];v[j]=aux;
	sort(v+1,v+n,cmp);
	q[0]=0;
	q[1]=1;
	k=2;
	for(i=2;i<n;i++)
	{
		q[k]=i;
		ok=check(v[q[k-2]],v[q[k-1]],v[q[k]]);
		while(!ok)
		{
			k--;
			q[k]=i;
			ok=check(v[q[k-2]],v[q[k-1]],v[q[k]]);
		}
		k++;
	}
	//printf("%f  %f",(asin(sqrt(3)/2)) ,3.14159265/3);
	printf("%d\n",k);
	for(i=0;i<k;i++) printf("%.2f %.2f\n", v[q[i]].x,v[q[i]].y);
	return 0;
}