Cod sursa(job #752173)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 27 mai 2012 23:02:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<limits.h>
#define dim 120007
using namespace std;
int stiv[dim],srt[dim],n;
double x[dim],y[dim];
int idx,PunctInitial,i;
bool cmpt(int i ,int j) {
	
	return (double)(x[i]-x[PunctInitial])*(y[j]-y[PunctInitial ]) <(double)(x[j]-x[PunctInitial])*(y[i]-y[PunctInitial ]);
}
long double unghi(int a,int b,int c)
{
	return (long double)x[a] * y[b] + x[b] * y[c] + x[c] * y[a] - y[a] * x[b] - y[b] * x[c] - y[c] * x[a];
}

int main (){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	x[0]=y[0]=10000000;
	PunctInitial=idx=0;
	for(i=1;i<=n;i++){
		scanf("%lf %lf",&x[i],&y[i]);
		if(x[i]<x[idx]  || (x[i]==x[idx]  && y[i]<y[idx]))
			idx=i;
		
	}
	PunctInitial=idx;
	for(i=1;i<=n;i++){
		if(i==PunctInitial)continue;
		srt[++srt[0]]=i;
	}
	sort(srt+1,srt+srt[0]+1,cmpt);
	stiv[0]=1;
	stiv[1]=PunctInitial;
	for(i=1;i<=srt[0];i++){
		
		if(srt[i]==PunctInitial)continue;
		
		while( stiv[0]>=2  && unghi(stiv[stiv[0]-1],stiv[stiv[0]],srt[i])>0 )
			--stiv[0];
		stiv[++stiv[0]]=srt[i];
	}
	stiv[++stiv[0]]=PunctInitial;
	printf("%d\n",stiv[0]-1);
	reverse(stiv+1,stiv+1+stiv[0]);
	for(i=1;i<=stiv[0]-1;i++)
		printf("%lf %lf\n",x[stiv[i]],y[stiv[i]]);
	return 0;
}