Pagini recente » Cod sursa (job #1436588) | Cod sursa (job #2510429) | Cod sursa (job #1841546) | Cod sursa (job #167501) | Cod sursa (job #2542442)
#include <bits/stdc++.h>
#define ll long long
#define inf (1LL<<62)
using namespace std;
const int nmax=255;
struct pct
{
int x,y,i;
}aux[nmax];
vector<pct>v,a,b;
vector<char>s;
int hull[nmax];
bool viz[nmax];
bool mycmp(pct a,pct b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
ll cross(pct x,pct y,pct z)
{
return (ll)(y.x-x.x)*(z.y-x.y)-(ll)(y.y-x.y)*(z.x-x.x);
}
void build_pcts(vector<pct>&a,vector<pct>&b,int poz1,int poz2,int n)
{
a.clear();
b.clear();
for(int i=0; i<n; i++)
{
if(poz1==i)
a.push_back(v[i]);
if(poz2==i)
b.push_back(v[i]);
if(poz1!=i and poz2!=i)
if(cross(v[poz1],v[poz2],v[i])>0)
a.push_back(v[i]);
else
b.push_back(v[i]);
}
}
void replace_sol(vector<char>&s,vector<pct>&a,vector<pct>&b,int n,bool iseq)
{
vector<char>aux;
aux.resize(n+1);
for(pct x:a)
aux[x.i]='I';
for(pct y:b)
aux[y.i]='V';
if(aux[0]=='V')
for(int i=0; i<n; i++)
aux[i]=((aux[i]=='V')?'I':'V');
if(iseq)
{
bool ok=false;
for(int i=0; i<n; i++)
if(aux[i]<s[i])
{
ok=true;
break;
}
else if(aux[i]>s[i])
break;
if(ok==true)
for(int i=0;i<n;i++)
s[i]=aux[i];
}
else
{
for(int i=0; i<n;i++)
s[i]=aux[i];
}
}
ll area(vector<pct>&v)
{
ll ans=0;
for(int i=0;i<v.size();i++)
ans+=cross({0,0,0},v[i],v[(i+1)%(int)v.size()]);
return fabs(ans);
}
bool ok(vector<pct>&v)
{
if(v.size()<=2)
return 0;
memset(viz,0,sizeof(viz));
int dir=1,k=-1;
for(int i=0;i>=0;i+=dir)
if(!viz[i])
{
while(k>=1 and cross(v[hull[k-1]],v[hull[k]],v[i])<0)
viz[hull[k--]]=0;
hull[++k]=i;
viz[i]=1;
if(i==v.size()-1)
dir=-1;
}
if(k+1!=v.size() or cross(v[hull[k-1]],v[hull[k]],v[0])<0)
return 0;
for(int i=0;i<v.size();i++)
aux[i]=v[hull[i]];
for(int i=0;i<v.size();i++)
v[i]=aux[i];
return 1;
}
int main()
{
ifstream cin("gradina.in");
ofstream cout("gradina.out");
ll mn=inf;
int n;
cin>>n;
v.resize(n);
s.resize(n);
for(int i=0; i<n; i++)
cin>>v[i].x>>v[i].y,v[i].i=i;
sort(v.begin(),v.end(),mycmp);
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
{
build_pcts(a,b,i,j,n);
if(ok(a) and ok(b))
{
if(fabs(area(a)-area(b))<=mn)
{
replace_sol(s,a,b,n,(fabs(area(a)-area(b))==mn));
mn=fabs(area(a)-area(b));
}
}
}
cout<<fixed<<setprecision(1)<<mn/2.0<<"\n";
for(int i=0;i<s.size();i++)
cout<<s[i];
return 0;
}