Cod sursa(job #302361)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 8 aprilie 2009 20:34:00
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define Nmax 121100
#define Inf 0x3f3f3f3f

double x[Nmax],y[Nmax];
int st[Nmax];
int n,poz,k;
int a[Nmax];

	
inline bool comp(int i,int j)   
{   
    return (x[i]-x[poz])*(y[j]-y[poz])<(x[j]-x[poz])*(y[i]-y[poz]);   
}   


double arie(int a, int b, int c)   
    {   
    return x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-y[b]*x[c]-y[c]*x[a]-y[a]*x[b];   
    }   

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

	poz=0;
	x[poz]=Inf;
	y[poz]=Inf;
	for (i=1;i<=n;++i)
		 if ((x[i]<x[poz]) || (x[i]==x[poz] && y[i]<y[poz]))
		 {
			poz=i;
		 }
		 
	for (i=1;i<=n;++i)
		if(i!=poz)
			a[++a[0]]=i;
	
	sort(a+1,a+a[0]+1,comp);
	st[++k]=poz;
	st[++k]=a[0];
		for (i=1;i<=a[0];++i)
	{
		while(k>1 && arie(st[k-1],st[k],a[i])>0)
			 k--;
		st[++k]=a[i];
	}
	
	printf("%d\n", k);
	for (i=k;i>=1;--i)
		 printf("%.4lf %.4lf\n", x[st[i]],y[st[i]]);
	return 0;
}