Pagini recente » Cod sursa (job #3291057) | Cod sursa (job #3272479) | Cod sursa (job #1038530) | Cod sursa (job #1346264) | Cod sursa (job #1336013)
#include <cstdio>
#include <algorithm>
FILE* in=fopen("gradina.in","r");
FILE* out=fopen("gradina.out","w");
const int Q=260,INF=2000000000;
int n;
struct point{
int x,y;
} v[Q];
void swap(int &a, int &b)
{
a^=b;
b^=a;
a^=b;
}
long long arie(int t[])
{
long long rez=0;
long long low=INF;
for(int i=1; i<=t[0]; i++)
{
if(v[t[i]].y<low)
low=v[t[i]].y;
}
for(int i=2; i<=t[0]; i++)
{
rez+=(long long)(v[t[i-1]].y-low+v[t[i]].y-low)*(v[t[i]].x-v[t[i-1]].x);
}
rez+=(long long)(v[t[t[0]]].y-low+v[t[1]].y-low)*(v[t[1]].x-v[t[t[0]]].x);
return rez;
}
point eta;
bool clock(point a, point b, point c)
{
long long aux;
aux=(long long)(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
return aux>0;
}
bool cmp(const int &a,const int &b)
{
return clock(v[a],v[b],eta);
}
int stv[Q];
bool infas(int t[])
{
eta.x=INF;
for(int i=1; i<=t[0]; i++)
{
if(v[t[i]].x<eta.x)
{
eta.x=v[t[i]].x;
eta.y=v[t[i]].y;
}
}
std::sort(t+1,t+t[0]+1,cmp);
for(int i=3; i<=t[0]; i++)
{
if(!clock(v[t[i-2]],v[t[i-1]],v[t[i]]))
{
return 0;
}
}
return 1;
}
int g[2][Q];
int min=INF;
char rez[Q];
void ver_rez()
{
std::sort(g[0]+1,g[0]+g[0][0]+1);
std::sort(g[1]+1,g[1]+g[1][0]+1);
char c[2];
if(g[0][1]==1)
{
c[0]='I';
c[1]='V';
}
else
{
c[0]='V';
c[1]='I';
}
int l1=1,l2=1;
g[0][g[0][0]+1]=INF;
g[1][g[1][0]+1]=INF;
bool bun=0;
for(int nxt=1; nxt<=n; nxt++)
{
if(g[0][l1]==nxt)
{
if(rez[nxt]=='V')
{
bun=1;
rez[nxt]='I';
}
}
else
{
if(rez[nxt]=='I' && bun==0)
{
return;
}
rez[nxt]='V';
}
}
}
void act_rez()
{
std::sort(g[0]+1,g[0]+g[0][0]+1);
std::sort(g[1]+1,g[1]+g[1][0]+1);
char c[2];
if(g[0][1]==1)
{
c[0]='I';
c[1]='V';
}
else
{
c[0]='V';
c[1]='I';
}
for(int i=1; i<=g[0][0]; i++)
{
rez[g[0][i]]=c[0];
}
for(int i=1; i<=g[1][0]; i++)
{
rez[g[1][i]]=c[1];
}
}
int mod(int x)
{
return x>0?x:-x;
}
void testeaza()
{
if(infas(g[0]) && infas(g[1]))
{
long long a1,a2;
a1=arie(g[0]);
a2=arie(g[1]);
if(mod(a1-a2)<min)
{
min=mod(a1-a2);
act_rez();
}
else if(mod(a1-a2)==min)
{
ver_rez();
}
}
}
void generat(int t, int p)
{
g[0][0]=0;
g[1][0]=0;
long long a,b,c;
a=v[p].y-v[t].y;
b=v[t].x-v[p].x;
c=(long long)v[p].x*v[t].y-(long long)v[t].x*v[p].y;
for(int i=1; i<=n; i++)
{
if(i!=t && i!=p)
{
if((long long)a*v[i].x+(long long)b*v[i].y+c>0)
{
g[0][++g[0][0]]=i;
}
else
{
g[1][++g[1][0]]=i;
}
}
}
g[0][0]++;
g[1][0]++;
if(g[0][0]<3 || g[1][0]<3)
return;
g[0][g[0][0]]=t;
g[1][g[1][0]]=p;
testeaza();
for(int i=1; i<=g[0][0]; i++)
{
if(g[0][i]==t)
{
g[0][i]=p;
break;
}
}
for(int i=1; i<=g[1][0]; i++)
{
if(g[1][i]==p)
{
g[1][i]=t;
break;
}
}
testeaza();
}
int main()
{
fscanf(in,"%d",&n);
for(int i=1; i<=n; i++)
{
fscanf(in,"%d%d",&v[i].x,&v[i].y);
}
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
generat(i,j);
}
}
fprintf(out,"%d",min/2);
if(min&1)
fprintf(out,".5");
else
fprintf(out,".0");
fprintf(out,"\n");
fputs(rez+1,out);
return 0;
}