Cod sursa(job #250928)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 1 februarie 2009 12:24:43
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
struct point{int x,y;};
int n,ns[2],i,i1,i2,p,q,H[351],minmax,maxmin,ok;
point a[351],as[2][351];
char ch[355],sol[355],cha[355];
long long s1,s2,ds,dsmin=(long long)(1<<31)*(1<<31);

bool cmp (point P1, point P2){
	if (P1.x==P2.x)return (P1.y<P2.y);
	else return (P1.x<P2.x);
}
inline long long isLeft(point P1, point P2,point P){
	return (long long)(P2.x-P1.x)*(P.y-P1.y)- (P.x-P1.x)*(P2.y-P1.y);
}
inline long long cross (point p1, point p2){
  return ((long long)p1.x * p2.y - p2.x * p1.y);
}
long long graham (int K){
  int i;long long S=0;
  //test imput
  if (ns[K]<3)return 0;
  //get the min,max and max,min points
	for (i=1; i<=ns[K] && as[K][i].x==as[K][1].x ;++i);minmax=i-1;
	for (i=ns[K]; i && as[K][i].x==as[K][ns[K]].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( as[K][1] , as[K][maxmin] , as[K][i] ) >=0 && i < maxmin ) continue;
		 while (q>1){
				if ( isLeft( as[K][ H[q-1] ], as[K][ H[q] ], as[K][i] ) > 0 ) break;
				q--;
		 }
		 H[++q]=i;
	}
	//upper Hull
	if ( maxmin != ns[K] ) H[++q] = ns[K];
	p = q;
	i = maxmin;
	while ( --i >= minmax ){
		 if ( isLeft( as[K][ns[K]], as[K][minmax], as[K][i] ) >= 0 && i > minmax )continue;
		 while (q > p){
				if ( isLeft( as[K][ H[q-1] ], as[K][ H[q] ], as[K][i] ) > 0 )break;
				q--;
		 }
		 H[++q]=i;
	}
	if (minmax==1) q--;
  if (q!=ns[K])ok=0;
  //calculate the polygon area
  for (i=1;i<q;++i)S+=cross(as[K][H[i]],as[K][H[i+1]]);
  S+=cross(as[K][H[q]],as[K][H[1]]);
return S;
}
int main(){
  freopen("gradina.in","r",stdin);
  freopen("gradina.out","w",stdout);
  scanf("%d",&n); long long k;
  for (i=1;i<=n;++i) scanf("%d %d",&a[i].x,&a[i].y);
  sort (a+1,a+n+1,cmp);
  for (i1=1;i1<n;++i1)
	 for (i2=i1+1;i2<=n;++i2){
		 //impartirea punctelor de o parte si alta a dreptei a[i1] a[i2]
		 ns[0]=0;ns[1]=0;
		 for (i=1;i<=n;++i){
		   k = isLeft( a[i1], a[i2], a[i] );	
			 if ( k < 0 ) as[0][++ns[0]]=a[i],ch[i]='I';
			 else if ( k > 0) as[1][++ns[1]]=a[i],ch[i]='V';
			 else if (i==i1) as[0][++ns[0]]=a[i],ch[i]='I'; else as[1][++ns[1]]=a[i],ch[i]='V';
		 }
		 //aplicare algoritm Graham
     ok=1;
     ds=graham(0)-graham(1);
     if (!ok)continue;
     if (ds<0)ds=-ds;
     if (ds<dsmin){dsmin=ds;strcpy(sol+1,ch+1);}
     else if (dsmin==ds) if (strcmp(ch+1,sol+1)<0)strcpy(sol+1,ch+1);
  }
  if ((dsmin&1)==1)printf("%lld.5\n",dsmin/2);
  else printf("%lld.0\n",dsmin/2);
  printf("%s\n",sol+1);
return 0;
}