Cod sursa(job #250274)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 30 ianuarie 2009 15:04:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#include <algorithm>
#define absd(a) ((a)<0?-(a):(a))
#define eps 0.0000000001
using namespace std;
struct point{double x,y;};
int n,i,p,q,H[120005],minmax,maxmin;
point a[120005];

bool cmp (point P1, point P2){
	 if (absd(P1.x-P2.x)<eps)return (P1.y<P2.y);
	 else return (P1.x<P2.x);
}
inline double isLeft(point P1, point P2,point P){
	 return (P2.x-P1.x)*(P.y-P1.y)- (P.x-P1.x)*(P2.y-P1.y);
}
int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%ld",&n);
	for (i=1;i<=n;++i) scanf("%lf %lf\n",&a[i].x,&a[i].y);
	sort (a+1,a+n+1,cmp);
	/*for (i=1;i<=n;++i)
	 printf("%lf %lf\n",a[i].x,a[i].y);*/
	//get the min,max and max,min points
	for (i=1; i<=n && a[i].x==a[1].x ;++i);minmax=i-1;
	for (i=n; i && a[i].x==a[n].x ;--i);maxmin=i+1;
	//lower Hull
	p=1; q=0; H[++q]=1;//min,min point...n is the max,max point
	i=minmax;
	while ( ++i <= maxmin ){
		 if ( isLeft( a[1] , a[maxmin] , a[i] ) >=0 && i < maxmin ) continue;
		 while (q>1){
				if ( isLeft( a[ H[q-1] ], a[ H[q] ], a[i] ) > 0 ) break;
				q--;
		 }
		 H[++q]=i;
	}
	//upper Hull
	if ( maxmin != n ) H[++q] = n;
	p = q;
	i = maxmin;
	while ( --i >= minmax ){
		 if ( isLeft( a[n], a[minmax], a[i] ) >= 0 && i > minmax )continue;
		 while (q > p){
				if ( isLeft( a[ H[q-1] ], a[ H[q] ], a[i] ) > 0 )break;
				q--;
		 }
		 H[++q]=i;
	}
	//if (minmax!=1) H[++q] = 1;
	printf("%ld\n",q);
	for (i=1;i<=q;++i)
		 printf("%lf %lf\n",a[H[i]].x , a[H[i]].y );

return 0;
}