Cod sursa(job #672769)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 3 februarie 2012 02:35:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<cstdio>
#include<algorithm>
#define Nmax 120010
#define INF 1<<30
using namespace std;

int i,n,k,s[Nmax],poz;

struct punct 
{
	double x,y,panta;
} v[Nmax],o,aux;

int cmp ( punct a, punct b)
{
	if(a.panta==b.panta) return a.x<b.x;
	
	return a.panta<b.panta;
}

int convex()
{
	punct a,b,c;
	double S;
	
	a=v[s[k-1]];
	b=v[s[k]];
	c=v[i];
	
	S = ( a.x-c.x ) * ( b.y-a.y ) + ( a.x-b.x ) * ( a.y-c.y ) ;
	
	if(S>0) return 1;
	return 0;
}


int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%d",&n);
	
	o.x=o.y=INF;
	
	for(i=1;i<=n;i++)
	{
		scanf("%lf %lf",&v[i].x,&v[i].y);
		
		if(v[i].x < o.x || v[i].x == o.x && v[i].y < o.y)
			o=v[i],poz=i;
	}
	
	aux=v[1]; v[1]=v[poz]; v[poz]=aux;
	
	for(i=2;i<=n;i++)
		v[i].panta = ( v[i].y - o.y ) / (v[i].x - o.x);
	
	sort(v+2,v+n+1,cmp);
	
	s[1]=1; s[2]=2; k=2;
	
	for(i=3;i<=n;i++)
	{
		while ( !convex() && k>2 ) k--;
		s[++k]=i;
	}
	
	printf("%d\n",k);
	
	for(i=1;i<=k;i++)
		printf("%0.6lf %0.6lf\n",v[s[i]].x,v[s[i]].y);
	return 0;
}