Pagini recente » Cod sursa (job #1067738) | Cod sursa (job #1239765) | Cod sursa (job #262808) | Cod sursa (job #2693015) | Cod sursa (job #3247302)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
char r[250],crt[250];
long long mini=LONG_LONG_MAX;
int n;
struct Punct
{
long long x,y;
int index;
bool t,side;
} pct[250];
vector <Punct> s0,s1;
bool sortpct(Punct a, Punct b)
{
return(a.x<b.x || (a.x==b.x && a.y<b.y));
}
long long Arie(Punct a,Punct b,Punct c)
{
return (a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x);
}
bool lexcomp(char a[],char b[])
{
for(int i=0;i<n;i++)
if(a[i]>b[i])
return 0;
else if(a[i]<b[i])
return 1;
return 1;
}
void infasuratoare()
{
s0.clear(),s1.clear();
for(int i=0; i<n; i++)
pct[i].t=0;
int s0p0=-1,s0p1=-1,s1p0=-1,s1p1=-1;
for(int i=0; i<n; i++)
if(pct[i].side==0)
{
if(s0p0==-1)
s0p0=i;
s0p1=i;
}
else
{
if(s1p0==-1)
s1p0=i;
s1p1=i;
}
for(int i=0; i<n; i++)
if(pct[i].side==0)
{
if(i==s0p0 || i==s0p1)
continue;
long long arie=Arie(pct[s0p0],pct[s0p1],pct[i]);
pct[i].t=(arie>0);
}
else
{
if(i==s1p0 || i==s1p1)
continue;
long long arie=Arie(pct[s1p0],pct[s1p1],pct[i]);
pct[i].t=(arie>0);
}
for(int i=0; i<n; i++)
if(pct[i].side==0)
{
if(pct[i].t)
continue;
while(s0.size()>=2)
{
long long arie=Arie(s0[s0.size()-2],s0[s0.size()-1],pct[i]);
if(arie<0)
return;
else break;
}
s0.push_back(pct[i]);
}
else
{
if(pct[i].t)
continue;
while(s1.size()>=2)
{
long long arie=Arie(s1[s1.size()-2],s1[s1.size()-1],pct[i]);
if(arie<0)
return;
else break;
}
s1.push_back(pct[i]);
}
int s0size0=s0.size()-1,s1size0=s1.size()-1;
pct[s0p0].t=pct[s1p0].t=1;
for(int i=n-1; i>=0; i--)
if(pct[i].side==0)
{
if(!pct[i].t)
continue;
while(s0.size()-s0size0>=2)
{
long long arie=Arie(s0[s0.size()-1],s0[s0.size()-2],pct[i]);
if(arie>0)
return;
else break;
}
s0.push_back(pct[i]);
}
else
{
if(!pct[i].t)
continue;
while(s1.size()-s1size0>=2)
{
long long arie=Arie(s1[s1.size()-1],s1[s1.size()-2],pct[i]);
if(arie>0)
return;
else break;
}
s1.push_back(pct[i]);
}
long long arie0=0,arie1=0;
if(s0.size())
{
s0.pop_back();
for(int i=1; i<s0.size()-1; i++)
arie0+=abs(Arie(s0[i],s0[i+1],s0[0]));
}
if(s1.size())
{
s1.pop_back();
for(int i=1; i<s1.size()-1; i++)
arie1+=abs(Arie(s1[i],s1[i+1],s1[0]));
}
if(abs(arie0-arie1)<mini)
{
mini=abs(arie0-arie1);
for(int i=0;i<n;i++)
if(pct[i].side==0)
r[pct[i].index]='I';
else r[pct[i].index]='V';
for(int i=0;i<n;i++)
if(pct[i].side==0)
crt[pct[i].index]='V';
else crt[pct[i].index]='I';
if(!lexcomp(r,crt))
strcpy(r,crt);
}
else if(abs(arie0-arie1==mini))
{
for(int i=0;i<n;i++)
if(pct[i].side==0)
crt[pct[i].index]='I';
else crt[pct[i].index]='V';
if(!lexcomp(r,crt))
strcpy(r,crt);
for(int i=0;i<n;i++)
if(pct[i].side==0)
crt[pct[i].index]='V';
else crt[pct[i].index]='I';
if(!lexcomp(r,crt))
strcpy(r,crt);
}
}
void dreapta(int p1,int p2)
{
for(int i=0; i<n; i++)
{
if(i==p1 || i==p2)
continue;
long long arie=Arie(pct[p1],pct[p2],pct[i]);
pct[i].side=(arie>0);
}
///0 0
infasuratoare();
pct[p1].side=1;
///1 0
infasuratoare();
pct[p1].side=0;
pct[p2].side=1;
///0 1
infasuratoare();
pct[p1].side=pct[p2].side=1;
///1 1
infasuratoare();
pct[p1].side=pct[p2].side=0;
}
int main()
{
int x,y;
fin>>n;
for(int i=0; i<n; i++)
{
fin>>x>>y;
pct[i]= {x,y};
pct[i].index=i;
}
sort(pct,pct+n,sortpct);
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
{
dreapta(i,j);
//cout<<i<<" "<<j<<endl;
}
fout<<fixed<<setprecision(1)<<(float)mini/2<<setprecision(0)<<'\n'<<r;
return 0;
}