Pagini recente » Cod sursa (job #1140098) | Cod sursa (job #2405105) | Cod sursa (job #1089677) | Cod sursa (job #149390) | Cod sursa (job #1096522)
#include <algorithm>
#include <cstdio>
#include <bitset>
#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];
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;
double arie1, arie2, sol=10000000000;
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(i=1;i<=p[0][0];i++) soli[p[0][i]]='I';
for(i=1;i<=p[1][0];i++) soli[p[1][i]]='V';
}
}
}
printf("%.1lf\n%s", sol, soli+1);
}