Cod sursa(job #67717)
Utilizator | Data | 25 iunie 2007 13:39:06 | |
---|---|---|---|
Problema | Gradina | Scor | 10 |
Compilator | cpp | Status | done |
Runda | preONI 2007, Runda Finala, Clasa a 10-a | Marime | 6.2 kb |
#include<algorithm>
#include<stdio.h>
using namespace std;
const int maxn = 501;
typedef int sir[maxn];
double x[maxn];
double y[maxn];
int n;
int i;
int j;
int k;
sir st[3];
sir sti;
sir ans;
sir ver;
double sol;
double modul(double x)
{
return x > 0 ? x : -x;
}
bool dr(int i,int j,int p1,int p2)
{
if ((x[i] * y[j] + x[j] * y[p1] + x[p1] * y[i] - y[i] * x[j] - y[j] * x[p1] - y[p1] * x[i] < 0) != (x[i] * y[j] + x[j] * y[p2] + x[p2] * y[i] - y[i] * x[j] - y[j] * x[p2] - y[p2] * x[i] < 0)) return 0;
return 1;
}
double unghi(int i,int j)
{
if (y[j] - y[i] == 0) return 1000000;
return x[i] - x[j] / y[i] - y[j];
}
bool cmpf(const int i,const int j)
{
return x[i] < x[j];
}
double convex_hull(sir &x1)
{
int i;
memset(ver,0,sizeof(ver));
memset(sti,0,sizeof(sti));
sort(x1 + 1,x1 + x1[0] + 1,cmpf);
sti[0]++;
sti[sti[0]] = x1[1];
sti[0]++;
ver[x1[1]] = 1;
ver[x1[2]] = 1;
sti[sti[0]] = x1[2];
for(i = 3;i <= x1[0]; ++i)
{
while(modul(unghi(sti[sti[0] - 1],sti[sti[0]])) < modul(unghi(sti[sti[0] -1],x1[i])) && sti[0] >= 2 )
{
ver[sti[sti[0]]] = 0;
sti[0]--;
}
sti[0]++;
sti[sti[0]] = x1[i];
ver[x1[i]] = 1;
}
int aux = sti[0];
for(i = x1[0]; i; --i)
{
if (!ver[x1[i]])
{
sti[0]++;
sti[sti[0]] = x1[i];
}
if (sti[0] - aux >= 2 && (unghi(sti[sti[0] - 2],sti[sti[0] - 1]) > unghi(sti[sti[0] - 2],x1[i])))
{
return -1;
}
}
double arie = 0;
sti[0]++;
sti[sti[0]] = sti[1];
for(i = 1;i <= sti[0]; ++i)
{
arie += x[sti[i]] * y[sti[i + 1]] - x[sti[i + 1]] * y[sti[i]];
}
return modul(arie);
}
int main()
{
freopen("gradina.in","r",stdin);
freopen("gradina.out","w",stdout);
scanf("%d",&n);
for(i = 1;i <= n; ++i)
{
scanf("%lf %lf",&x[i],&y[i]);
}
sol = 1000000;
for(i = 1;i <= n; ++i)
{
for(j = i + 1;j <= n; ++j)
{
memset(st,0,sizeof(st));
for(k = 1;k <= n; ++k)
{
if (k == i || k == j) continue;
if (dr(i,j,k,st[1][1]) || st[1][0] == 0)
{
st[1][0]++;
st[1][st[1][0]] = k;
}
else
{
st[2][0]++;
st[2][st[2][0]] = k;
}
}
for(k = 1;k <= 2; ++k)
{
st[k][0]++;
st[k][st[k][0]] = i;
st[k][0]++;
st[k][st[k][0]] = j;
double o1 = convex_hull(st[1]);
double o2 = convex_hull(st[2]);
if (o1 != -1 && o2 != -1)
{
if (sol > modul(o1 - o2))
{
sol = modul(o1 - o2);
int i1;
memset(ans,0,sizeof(ans));
for(i1 = 1;i1 <= st[1][0]; ++i1)
ans[st[1][i1]] = 1;
}
}
int i1;
for(i1 = 1;i1 <= st[k][0]; ++i1)
{
if (st[k][i1] == i)
{
break;
}
}
for(;i1 <= st[k][0]; ++i1)
{
st[k][i1] = st[k][i1 + 1];
}
for(i1 = 1;i1 <= st[k][0]; ++i1)
{
if (st[k][i1] == j)
{
break;
}
}
for(;i1 <= st[k][0]; ++i1)
{
st[k][i1] = st[k][i1 + 1];
}
st[k][0] -= 2;
}
}
}
printf("%.1lf\n",sol);
int veri = 0;
if (ans[1] == 1) veri = 1;
for(i = 1;i <= n; ++i)
{
if (ans[i])
{
if (veri)
{
printf("I");
}
else
{
printf("V");
}
}
else
{
if (veri)
{
printf("V");
}
else
{
printf("I");
}
}
}
printf("\n");
return 0;
}