Cod sursa(job #477052)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 13 august 2010 11:14:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "infasuratoare.in"
#define file_out "infasuratoare.out"

#define nmax 123234

int n;
double x[nmax];
double y[nmax];
int poz;
int st[nmax];
int a[nmax];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (int i=1;i<=n;++i)
		 scanf("%lf %lf", &x[i], &y[i]);
}

int cmp(int i, int j)
{
	return (x[i]-x[poz])*(y[j]-y[poz])<(y[i]-y[poz])*(x[j]-x[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]-x[a]*y[c]-y[a]*x[b]); 
}

void solve()
{
	int i,k;
	poz=0;
	
	x[poz]=1000000.0;
	y[poz]=1000000.0;

	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,cmp);
    k=0;
    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("%.6lf %.6lf\n", x[st[i]],y[st[i]]);
}
int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}