Cod sursa(job #399433)

Utilizator BaduBadu Badu Badu Data 20 februarie 2010 14:49:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<cstdio>
#include<algorithm>
#include<math.h>
#define max 120000

using namespace std;

int N,Pi;
double X[max];
double Y[max];
int    I[max];
int    S[max];

int cmp( int i1, int i2 ){
	
	return ( (double) (X[i1]-X[Pi])*(Y[i2]-Y[Pi]) <  (double) (X[i2]-X[Pi])*(Y[i1]-Y[Pi]));
}

long double semn( int p1, int p2, int p3){
	
	return (long double) X[p1]*Y[p2] + X[p2]*Y[p3] + X[p3]*Y[p1] - Y[p2]*X[p3] - X[p1]*Y[p3] - X[p2]*Y[p1];
}

int main(){
	
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%d",&N);
	int i;
	double Px,Py;
	Px=Py=1000000001;
	
	for(i=1;i<=N;i++){
		scanf("%lf %lf",&X[i],&Y[i]);
		if( X[i] < Px || ( X[i] == Px && Y[i] < Py ) ) { 
			Pi = i;
			Py = Y[i];
			Px = X[i];
		}
	}
	
	for(i=1;i<=N;i++){
		if( i==Pi ) continue;
		I[++I[0]]=i;
	}
	
	sort( I + 1 , I  + I[0] + 1, cmp);
	
	S[++S[0]] = Pi;
	
	for( i=1;i<=I[0];i++){
		
		if( I[i] == Pi ) continue;
		while( S[0]>=2 && semn( S[S[0]-1] , S[S[0]], I[i] ) > 0 ) S[0]--;
		S[++S[0]] = I[i];
	}
	
	printf("%d\n",S[0]);
	S[++S[0]] = Pi;
	for(i = S[0]-1; i>1; i-- ) printf("%lf %lf\n",X[S[i]],Y[S[i]]);
	printf("%lf %lf\n",Px,Py);


	return 0;
}