Cod sursa(job #729609)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 29 martie 2012 19:17:06
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include<stdio.h>
#include<cstring>
#include<algorithm>

#define maxn 253
#define INF (1<<29)

using namespace std;

FILE*f=fopen("gradina.in","r");
FILE*g=fopen("gradina.out","w");

int n;
int St[maxn],vf;
char P[maxn],Sol[maxn];
long long sol = 1LL<<62;

struct pct{
	int x,y;
	double ctg;
}A[maxn],P1[maxn],P2[maxn];

inline long long det ( const pct &a , const pct &b , const pct &c ){
	long long d = 1LL*(a.x-c.x)*(b.y-c.y) - 1LL*(b.x-c.x)*(a.y-c.y);
	return d;
}

struct cmp{
	inline bool operator () ( const pct &a , const pct &b ){
		return a.ctg > b.ctg;
	}
};

inline long long arie ( pct *A , int n ){
	
	int ymin = INF,xmin = INF,poz;
	for ( int i = 1 ; i <= n ; ++i ){
		if ( A[i].y < ymin ){
			ymin = A[i].y; xmin = A[i].x; poz = i;
		}
		else{
			if ( A[i].y == ymin && A[i].x < xmin ){
				xmin = A[i].x; poz = i;
			}
		}
	}
	
	pct aux = A[1]; A[1] = A[poz]; A[poz] = aux;
	for ( int i = 2 ; i <= n ; ++i ){
		A[i].ctg = (double)(A[i].x-xmin)/(A[i].y-ymin);
	}
	sort(A+2,A+n+1,cmp());
	
	vf = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		
		while ( vf >= 2 && det(A[St[vf-1]],A[St[vf]],A[i]) <= 0 ){
			St[vf] = 0; --vf;
		}
		
		St[++vf] = i;
	}
	
	if ( vf == n ){
		long long S = 0;
		for ( int i = 2 ; i < n ; ++i ){
			long long now = det(A[1],A[i],A[i+1]); if ( now < 0 )	now = -now;
			S += now;
		}
		return S;
	}
	else{
		return -1;
	}
}

inline void check ( const long long &a1 , const long long &a2 ){
	if ( a1 == -1 || a2 == -1 )	return ;
	
	long long dif = a1 - a2; if ( dif < 0 )	dif = -dif;
	
	if ( dif < sol ){
		sol = dif;
		for ( int i = 1 ; i <= n ; ++i ){
			Sol[i] = P[i];
		}
	}
	else{
		if ( dif == sol && strcmp(P+1,Sol+1) < 0 ){
			for ( int i = 1 ; i <= n ; ++i ){
				Sol[i] = P[i];
			}
		}
	}
}

int main () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ;  i <= n ; ++i ){
		fscanf(f,"%d %d",&A[i].x,&A[i].y);
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= n ; ++j ){
			if ( i == j )	continue ;
			
			int n1 = 1,n2 = 1;
			P1[1] = A[i]; P2[1] = A[j]; P[i] = 'I'; P[j] = 'V';
			for ( int k = 1 ; k <= n ; ++k ){
				if ( k != i && k != j ){
					if ( det(A[i],A[j],A[k]) < 0 ){
						P1[++n1] = A[k]; P[k] = 'I';
					}
					else{
						P2[++n2] = A[k]; P[k] = 'V';
					}
				}
			}
			
			if ( n1 < 3 || n2 < 3 )	continue ;
			
			long long a1,a2;
			a1 = arie(P1,n1);
			a2 = arie(P2,n2);
			
			check(a1,a2);
		}
	}
	
	fprintf(g,"%.1lf\n",(double)sol/2);
	fprintf(g,"%s\n",Sol+1);
	
	fclose(f);
	fclose(g);
	
	return 0;
}