Pagini recente » Cod sursa (job #833095) | Cod sursa (job #1501378) | Cod sursa (job #1232863) | Cod sursa (job #2363805) | Cod sursa (job #1096524)
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <cstring>
#define EPS 1e-10
#define PII pair<double, double>
#define x first
#define y second
using namespace std;
const int N=255;
PII a[N];
bitset <N> v;
int inf[N], p[2][N];
char soli[N], aux[N];
double modul(double k)
{
if(k<0) return -k;
return k;
}
double sarr(PII o, PII a, PII b)
{
return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
struct comp
{
bool operator() (const int &b, const int &c) const
{
return a[b]<a[c];
}
};
double geta(int u)
{
double ret=0;
int n=p[u][0], i, sign=1;
sort(p[u]+1, p[u]+n+1, comp());
inf[0]=2; inf[1]=p[u][1]; inf[2]=p[u][2];
v.reset();
v[p[u][2]]=1;
for(i=1;i;i+=sign)
{
if(!v[p[u][i]])
{
while(inf[0]>1&&sarr(a[inf[inf[0]-1]], a[inf[inf[0]]], a[p[u][i]])<EPS)
{
v[inf[inf[0]--]]=0;
}
inf[++inf[0]]=p[u][i];
v[p[u][i]]=1;
}
if(i==n) sign=-1;
}
for(i=1;i<inf[0];i++)
{
ret+=a[inf[i]].x*a[inf[i+1]].y-a[inf[i]].y*a[inf[i+1]].x;
}
return ret/2;
}
int main()
{
freopen("gradina.in", "r", stdin);
freopen("gradina.out", "w", stdout);
int n, i, j, k, l;
double arie1, arie2, sol=1000000000000000LL;
scanf("%d", &n);
for(i=1;i<=n;i++) scanf("%lf%lf", &a[i].x, &a[i].y);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j) continue;
p[0][0]=p[1][0]=1;
p[0][1]=i;
p[1][1]=j;
for(k=1;k<=n;k++)
{
if(k==i||k==j) continue;
if(sarr(a[k], a[i], a[j])>0) p[0][++p[0][0]]=k;
else p[1][++p[1][0]]=k;
}
if(p[0][0]<3||p[1][0]<3) continue;
arie1=geta(0);
arie2=geta(1);
if(modul(arie1-arie2)<sol)
{
sol=modul(arie1-arie2);
for(l=1;l<=p[0][0];l++) soli[p[0][l]]='I';
for(l=1;l<=p[1][0];l++) soli[p[1][l]]='V';
}
else if(modul(modul(arie1-arie2)-sol)<EPS)
{
for(l=1;l<=p[0][0];l++) aux[p[0][l]]='I';
for(l=1;l<=p[1][0];l++) aux[p[1][l]]='V';
for(l=1;l<=n;l++)
{
if(soli[l]<aux[l]) break;
else if(soli[l]>aux[l])
{
memcpy(soli, aux, sizeof(aux));
break;
}
}
}
}
}
printf("%.1lf\n%s", sol, soli+1);
}