Cod sursa(job #527986)

Utilizator chrissBota Cristian chriss Data 1 februarie 2011 18:16:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#include <algorithm>
#define nmax 999999

using namespace std;

int n;
double x[nmax];
double y[nmax];
int poz, S[nmax], P[nmax];

void citire()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.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 produs(int a, int b, int c)
{
	return ((x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]));
}

void solve()
{
	int i,varf;
	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)
			  P[++P[0]]=i;

	sort(P+1,P+P[0]+1,cmp);
    varf=0;
    S[++varf]=poz;
	S[++varf]=P[0];
	for (i=1;i<=P[0];++i)
	{
		while(varf>1 && produs(S[varf-1],S[varf],P[i])>0) varf--;
		S[++varf]=P[i];
	}
	printf("%d\n", varf);
	for(i=varf;i>=1;--i)
		 printf("%.6lf %.6lf\n", x[S[i]],y[S[i]]);
}
int main()
{
	citire();
	solve();
	return 0;
}