Cod sursa(job #2076467)
Utilizator | Data | 26 noiembrie 2017 17:17:28 | |
---|---|---|---|
Problema | Gradina | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.21 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
long long minim=(1LL<<62);
struct punct
{
int x,y,z;
};
punct v[251],v1[251],v2[251];
bool 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(v[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);
sort(v+2,v+n+1,cmp1);
for(i=1; i<n; ++i)
{
for(j=i+1; j<=n; ++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];
else
v2[++nr2]=v[k];
}
if(nr1>=3&&nr2>=3)
{
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)
{
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<=nr1;++k)
{
sol[v1[k].z]=1;
}
for(k=1;k<=nr2;++k)
{
sol[v2[k].z]=0;
}
}
}
}
}
}
}
if(minim%2==0)
printf("%I64d.0\n",minim/2);
else
printf("%I64d.5\n",minim/2);
if(sol[1]==0)
{
for(i=1;i<=n;++i)
{
if(sol[i]==0)
printf("I");
else
printf("V");
}
}
else
{
for(i=1;i<=n;++i)
{
if(sol[i]==0)
printf("V");
else
printf("I");
}
}
return 0;
}