Pagini recente » Cod sursa (job #895829) | Cod sursa (job #2584586) | Cod sursa (job #2683152) | Cod sursa (job #2191811) | Cod sursa (job #2036422)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define MAXN 255
#define ll long long
using namespace std;
ifstream si("gradina.in");
ofstream so("gradina.out");
long long rez=-1;
int n,sol[2][MAXN];
char ans[MAXN],aux[MAXN];
struct myc
{
int x,y,z;
bool operator<(const myc u)const
{
if(x!=u.x)
return x<u.x;
else
return y<u.y;
}
}v[MAXN];
inline long long arie(int i,int j,int p)
{
return 1LL*v[i].x*v[j].y-1LL*v[j].x*v[i].y+1LL*v[j].x*v[p].y-1LL*v[p].x*v[j].y+1LL*v[p].x*v[i].y-1LL*v[i].x*v[p].y;
}
inline long long convex(int r[])
{
int a=0,b=1;
long long ans=0;
for(int i=2;i<r[0];i++)
{
if(arie(r[1],r[r[0]],r[i])>0)
{
if(a==0)
{
a=1;
b=i;
}
else
{
if(arie(r[a],r[b],r[i])>0)
return 0;
a=b;
b=i;
ans+=arie(r[1],r[b],r[a]);
}
}
}
if((a)&&(arie(r[a],r[b],r[r[0]])>0))
return 0;
a=b;
b=r[0];
if(a!=1)
ans+=arie(r[1],r[b],r[a]);
for(int i=r[0]-1;i>1;i--)
{
if(arie(r[1],r[r[0]],r[i])<0)
{
if(arie(r[a],r[b],r[i])>0)
return 0;
a=b;
b=i;
ans+=arie(r[1],r[b],r[a]);
}
}
if(arie(r[a],r[b],r[1])>0)
return 0;
return ans;
}
void solutie()
{
if(sol[0][0]<3)
return;
if(sol[1][0]<3)
return;
long long a1=convex(sol[0]);
if(a1==0)
return;
long long a2=convex(sol[1]);
if(a2==0)
return;
//cout<<a1<<' '<<a2;
if((rez==-1)||(abs(a1-a2)<rez))
{
rez=abs(a1-a2);
for(int i=1;i<=sol[0][0];i++)
ans[v[sol[0][i]].z]='I';
for(int i=1;i<=sol[1][0];i++)
ans[v[sol[1][i]].z]='V';
if(ans[0]=='V')
for(int i=0;i<n;i++)
if(ans[i]=='I')
ans[i]='V';
else
ans[i]='I';
}
else
if(abs(a1-a2)==rez)
{
for(int i=1;i<=sol[0][0];i++)
aux[v[sol[0][i]].z]='I';
for(int i=1;i<=sol[1][0];i++)
aux[v[sol[1][i]].z]='V';
if(aux[0]=='V')
for(int i=0;i<n;i++)
if(aux[i]=='I')
aux[i]='V';
else
aux[i]='I';
int p=0;
while((p+1<n)&&(aux[p]==ans[p]))
p++;
if(aux[p]<ans[p])
{
while(p<n)
{
ans[p]=aux[p];
p++;
}
}
}
}
int main()
{
si>>n;
for(int i=0;i<n;++i)
{
si>>v[i].x>>v[i].y;
v[i].z=i;
}
sort(v,v+n);
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
{
int l;
sol[0][0]=sol[1][0]=0;
for(int p=0;p<n;++p)
{
if(p!=i&&p!=j)
{
l=(arie(i,j,p)>0);
//cout<<l<<'\n';
sol[l][++sol[l][0]]=p;
}
else
if(p==i)
sol[0][++sol[0][0]]=p;
else
sol[1][++sol[1][0]]=p;
}
solutie();
}
so<<setprecision(1)<<fixed<<rez*0.5<<'\n';
for(int i=0;i<n;++i)
so<<ans[i];
return 0;
}