Pagini recente » Cod sursa (job #247954) | Cod sursa (job #66082) | Cod sursa (job #2395604) | Cod sursa (job #2766867) | Cod sursa (job #2610688)
#include <bits/stdc++.h>
#define nmax 152
using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
struct ceva
{
int x,y;
} t1[nmax],t2[nmax],a[nmax];
int n,aux,vft1,vft2,st[nmax];
char S[nmax],ch[nmax];
double Min;
bool marker[nmax];
bool cmp(ceva a,ceva b)
{
if(a.x>b.x)return false;
if(a.x==b.x && a.y>b.y)return false;
return true;
}
int det(ceva a,ceva b,ceva c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double functie(ceva p[],int m)
{
double sol=0;
for(int i=1; i<=m; i++)
{
marker[i]=false;
}
st[1]=1;
st[2]=2;
marker[2]=true;
int vf=2;
int poz=2;
int pas=1;
while(marker[1]==false)
{
while(marker[poz]==true)
{
poz+=pas;
if(poz==m)pas=-1;
}
while(vf>=2 && det(p[st[vf-1]],p[st[vf]],p[poz])<0)
{
marker[st[vf]]=false;
vf--;
}
vf++;
st[vf]=poz;
marker[poz]=true;
}
for(int i=1; i<vf; i++)
{
sol=sol+det(p[0],p[st[i]],p[st[i+1]]);
}
sol=sol/2;
if(vf!=m+1)
{
aux=0;
}
return sol;
}
void Solve()
{
Min=1000000000;
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
vft1=0;
vft2=0;
if(i==1||det(a[1],a[i],a[j])<0)
{
for(int k=1; k<=n; k++)
{
if(k==i || k==j || det(a[k],a[i],a[j])<0)
{
ch[k]='I';
vft1++;
t1[vft1]=a[k];
}
else
{
ch[k]='V';
vft2++;
t2[vft2]=a[k];
}
}
}
else
{
for(int k=1; k<=n; k++)
{
if(k==i || k==j || det(a[k],a[i],a[j])<0)
{
ch[k]='V';
vft2++;
t2[vft2]=a[k];
}
else
{
ch[k]='I';
vft1++;
t1[vft1]=a[k];
}
}
}
if(vft1<3 || vft2<3)continue;
sort(t1+1,t1+vft1+1,cmp);
sort(t2+1,t2+vft2+1,cmp);
aux=1;
double dif=abs(functie(t1,vft1)-functie(t2,vft2));
if(aux==0)continue;
if(dif<Min)
{
Min=dif;
for(int k=1; k<=n; k++)S[k]=ch[k];
}
}
}
g<<setprecision(1)<<fixed;
g<<Min<<'\n';
for(int i=1; i<=n; i++)
{
g<<S[i];
}
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
{
f>>a[i].x>>a[i].y;
}
Solve();
return 0;
}