Pagini recente » Cod sursa (job #1215274) | Cod sursa (job #2414707) | Cod sursa (job #2584869) | Cod sursa (job #1054269) | Cod sursa (job #1096549)
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <cstring>
#define EPS 1e-10
using namespace std;
const int N=255;
struct PII
{
double x, y;
int poz;
bool operator<(const PII &e) const
{
return (x==e.x?y<e.y:x<e.x);
}
};
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);
}
double geta(int u)
{
double ret=0;
int n=p[u][0], i, sign=1;
inf[0]=2; inf[1]=p[u][1]; inf[2]=p[u][2];
v.reset();
v[p[u][2]]=1;
for(i=3;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]])<0)
{
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=1e19L;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf", &a[i].x, &a[i].y);
a[i].poz=i;
}
sort(a+1, a+n+1);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j) continue;
p[0][0]=p[1][0]=0;
for(k=1;k<=n;k++)
{
if(k==i)
{
p[0][++p[0][0]]=k;
}
else if(k==j)
{
p[1][++p[1][0]]=k;
}
else 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[a[p[0][l]].poz]='I';
for(l=1;l<=p[1][0];l++) soli[a[p[1][l]].poz]='V';
}
else if(modul(modul(arie1-arie2)-sol)<EPS)
{
for(l=1;l<=p[0][0];l++) aux[a[p[0][l]].poz]='I';
for(l=1;l<=p[1][0];l++) aux[a[p[1][l]].poz]='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);
}