Pagini recente » Cod sursa (job #1792087) | Cod sursa (job #2811769) | Cod sursa (job #2537053) | Cod sursa (job #1694993) | Cod sursa (job #2163543)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define DN 255
#define x first
#define y second
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
int n,nr1,nr2,f[DN];
int r[DN],p,st[DN],top;
char c[DN];
typedef pair<double,double>pii;
double rez=1e18,t;
pii z[DN],a[DN],b[DN];
double det(pii A,pii B,pii 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;
}
double ve(pii a[DN],int n)
{
double s=0;
top=2;
st[1]=1;
st[2]=2;
for(int i=3;i<=n;i++)
{
while(top>1&&det(a[st[top-1]],a[st[top]],a[i])<0)
top--;
top++;
st[top]=i;
}
for(int i=n-1;i>=1;i--)
{
while(top>1&&det(a[st[top-1]],a[st[top]],a[i])<0)
top--;
top++;
st[top]=i;
}
for(int i=1;i<top;i++)
s+=det(a[0],a[st[i]],a[st[i+1]]);
s/=2;
return s;
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>z[i].x>>z[i].y;
sort(z+1,z+n+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
nr1=nr2=0;
if(i==1||det(z[1],z[i],z[j])<0)
{
for(int h=1;h<=n;h++)
if(h==i||det(z[h],z[i],z[j])<0)
{
f[h]=0;
nr1++;
a[nr1]=z[h];
}
else
{
f[h]=1;
nr2++;
b[nr2]=z[h];
}
}
else
{
for(int h=1;h<=n;h++)
if(h==i||det(z[h],z[i],z[j])<0)
{
f[h]=1;
nr2++;
b[nr2]=z[h];
}
else
{
f[h]=0;
nr1++;
a[nr1]=z[h];
}
}
if(min(nr1,nr2)<3)
continue;
t=abs(ve(a,nr1)-ve(b,nr2));
if(t==rez)
{
p=1;
for(int h=1;h<=n;h++)
if(f[h]<r[h])
break;
else
if(f[h]>r[h])
{
p=0;
break;
}
if(p)
for(int h=1;h<=n;h++)
r[h]=f[h];
continue;
}
if(t<rez)
{
rez=t;
for(int h=1;h<=n;h++)
r[h]=f[h];
}
}
for(int i=1;i<=n;i++)
if(r[i]==0)
c[i]='I';
else
c[i]='V';
fout<<fixed<<setprecision(1)<<rez<<'\n';
for(int i=1;i<=n;i++)
fout<<c[i];
}