Cod sursa(job #1826988)
Utilizator | Data | 11 decembrie 2016 11:59:06 | |
---|---|---|---|
Problema | Gradina | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 5.82 kb |
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long minim=(1LL<<62);
struct punct
{
int x,y,z;
};
punct v[251],v1[251],v2[251];
char sol1[251],sol[251];
bool cmp(punct a,punct b)
{
if(a.y==b.y)
return a.x<b.x;
else
return a.y<b.y;
}
long long cp(punct a,punct b,punct c)
{
return 1LL*a.x*b.y-1LL*a.y*b.x+1LL*b.x*c.y-1LL*b.y*c.x+1LL*c.x*a.y-1LL*c.y*a.x;
}
int ccw(punct a,punct b,punct c)
{
if(cp(a,b,c)>0)
return 1;
if(cp(a,b,c)<0)
return -1;
return 0;
}
bool cmp1(punct a,punct b)
{
return ccw(v1[1],a,b)>0;
}
bool cmp2(punct a,punct b)
{
return ccw(v2[1],a,b)>0;
}
int main()
{
freopen("gradina.in","r",stdin);
freopen("gradina.out","w",stdout);
int n,i,j,k,nr1,nr2;
long long arie1,arie2;
scanf("%d",&n);
for(i=1; i<=n; ++i)
{
scanf("%d%d",&v[i].x,&v[i].y);
v[i].z=i;
}
sort(v+1,v+n+1,cmp);
for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j)
{
if(i!=j)
{
nr1=0;
nr2=0;
for(k=1; k<=n; ++k)
{
if(ccw(v[i],v[j],v[k])>0||k==i)
{
v1[++nr1]=v[k];
sol1[v[k].z]='I';
}
else
{
v2[++nr2]=v[k];
sol1[v[k].z]='V';
}
}
if(nr1>=3&&nr2>=3)
{
sort(v1+2,v1+nr1+1,cmp1);
sort(v2+2,v2+nr2+1,cmp2);
bool ok=1;
for(k=3; k<=nr1; ++k)
{
if(ccw(v1[k-2],v1[k-1],v1[k])<1)
{
ok=0;
break;
}
}
if(ccw(v1[nr1-1],v1[nr1],v1[1])<1)
ok=0;
if(ccw(v1[nr1],v1[1],v1[2])<1)
ok=0;
if(ok)
{
for(k=3; k<=nr2; ++k)
{
if(ccw(v2[k-2],v2[k-1],v2[k])<1)
{
ok=0;
break;
}
}
if(ccw(v2[nr2-1],v2[nr2],v2[1])<1)
ok=0;
if(ccw(v2[nr2],v2[1],v2[2])<1)
ok=0;
if(ok)
{
if(sol1[1]=='V')
{
for(k=1; k<=n; ++k)
{
if(sol1[k]=='V')
sol1[k]='I';
else
sol1[k]='V';
}
}
arie1=0;
arie2=0;
for(k=1; k<nr1; ++k)
{
arie1+=(1LL*v1[k].x*v1[k+1].y);
arie1-=(1LL*v1[k].y*v1[k+1].x);
}
arie1+=(1LL*v1[nr1].x*v1[1].y);
arie1-=(1LL*v1[1].x*v1[nr1].y);
if(arie1<0)
arie1*=(-1);
for(k=1; k<nr2; ++k)
{
arie2+=(1LL*v2[k].x*v2[k+1].y);
arie2-=(1LL*v2[k].y*v2[k+1].x);
}
arie2+=(1LL*v2[nr2].x*v2[1].y);
arie2-=(1LL*v2[1].x*v2[nr2].y);
if(arie2<0)
arie2*=(-1);
long long arie=arie1-arie2;
if(arie<0)
arie*=(-1);
if(arie<minim)
{
minim=arie;
for(k=1; k<=n; ++k)
{
sol[k]=sol1[k];
}
}
else
{
if(arie==minim)
{
bool ok2=0;
for(k=1; k<=n; ++k)
{
if(sol1[k]<sol[k])
{
ok2=1;
break;
}
}
if(ok2)
{
for(k=1; k<=n; ++k)
{
sol[k]=sol1[k];
}
}
}
}
}
}
}
}
}
}
if(minim%2==0)
printf("%lld.0\n",minim/2);
else
printf("%lld.5\n",minim/2);
for(i=1; i<=n; ++i)
{
printf("%c",sol[i]);
}
return 0;
}