Pagini recente » Cod sursa (job #235471) | Cod sursa (job #690323) | Cod sursa (job #198847) | Cod sursa (job #2659551) | Cod sursa (job #729609)
Cod sursa(job #729609)
#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;
}