Cod sursa(job #508882)

Utilizator bog29Antohi Bogdan bog29 Data 9 decembrie 2010 20:38:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<algorithm>
#define dmax 120004
using namespace std;

int n,w,st[dmax],nr;

struct punct
{	double x;
	double y;
	double up;
}	p[dmax],t;
	
int sf(punct a, punct b)
{	if(a.up != b.up)
		return a.up < b.up;
	
	return a.x < b.x;
}

int pr(int p0, int p1, int p2)
{	double s = (p[p1].x-p[p0].x)*(p[p2].y-p[p0].y)-(p[p2].x-p[p0].x)*(p[p1].y-p[p0].y);
	
	if(s>0)return 1;
	return 0;
}
	

int main()
{	freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
	
	int i;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf %lf",&p[i].x,&p[i].y);
		
	w=1;
	for(i=2;i<=n;i++)
	{	if(p[i].x < p[w].x)
			w=i;
		else if(p[i].x == p[w].x)
			if(p[i].y < p[w].y)
				w=i;
	}
	
	t=p[1];
	p[1]=p[w];
	p[w]=t;
	
	for(i=2;i<=n;i++)
		p[i].up=(p[i].y-p[1].y)/(p[i].x-p[1].x);
	
	sort(p+2,p+n+1, sf);
	
	st[1]=1;
	st[2]=2;
	nr=2;
	
	for(i=3;i<=n;i++)
	{	while(!pr(	st[nr],i,st[nr-1]) && nr>2)
			nr--;

		st[++nr]=i;
	}
	
	printf("%d\n",nr);
	for(i=1;i<=nr;i++)
		printf("%0.6lf %0.6lf\n",p[st[i]].x,p[st[i]].y);
	
	return 0;
}