Cod sursa(job #411932)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 5 martie 2010 11:29:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 120005
#define INF 2147000000
#define ld long double
#define d double
using namespace std;

double x[Nmax],y[Nmax];
int ind[Nmax],st[Nmax],n,i,p;

int cmp(int i,int j){
	return( (d)(x[i]-x[p])*(y[j]-y[p]) < (d)(x[j]-x[p])*(y[i]-y[p]) );
}
ld semn(int i1,int i2,int i3){
	return (ld) (x[i2]-x[i1])*(y[i3]-y[i1]) - (x[i3]-x[i1])*(y[i2]-y[i1]);
}	

int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	
	x[p=0]=y[0]=INF;
	for(i=1;i<=n;++i){
		scanf("%lf%lf",&x[i],&y[i]);
		if( x[i] < x[p] || (x[i]==x[p] && y[i]<y[p]) ) p=i;
	}
	
	for(i=1;i<=n;++i)
		if(i!=p) ind[++ind[0]]=i;
	
	sort(ind+1,ind+ind[0]+1,cmp);
		
	st[st[0]=1]=p;
	for(i=1;i<=ind[0];++i){
		if( st[0]>1 && semn(st[st[0]-1],st[st[0]],ind[i])>0)
			st[0]--;
		st[++st[0]]=ind[i];
	}
	
	printf("%d\n",st[0]);
	reverse(st+1,st+st[0]+1);
	for(i=1;i<=st[0];++i) printf("%lf %lf\n",x[st[i]],y[st[i]]);
	
	fclose(stdin); fclose(stdout);
	return 0;
}