Pagini recente » Cod sursa (job #873841) | Cod sursa (job #1118032) | Cod sursa (job #1545020) | Cod sursa (job #1818008) | Cod sursa (job #589327)
Cod sursa(job #589327)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define pi pair<pair<int,int>,int>
#define x first.first
#define y first.second
#define ind second
#define NMAX 304
double INF=(double)1000000000*100000;
double sol=INF;
char viz[NMAX],p[NMAX],vec[NMAX];
pi v[NMAX],vp[NMAX];
int st[NMAX],n,vecc[NMAX];
inline int cmp(const pi& a,const pi& b)
{
return a.y<b.y;
}
inline int semn(pi A,pi B,pi C)
{
int a=A.y-B.y;
int b=B.x-A.x;
int c=B.y*A.x-A.y*B.x;
return C.x*a+C.y*b+c;
}
double infas(int tip)
{
int nr=0,i,sf;
for(i=1;i<=n;i++)
if(p[i]==tip)
vp[++nr]=v[i];
if(nr<3)
return INF;
st[1]=1;st[2]=2;
sf=2;
for(i=3;i<=nr;i++)
{
while(sf>1 && semn(vp[st[sf-1]],vp[st[sf]],vp[i])<0)
sf--;
st[++sf]=i;
}
memset(viz,0,sizeof(viz));
for(i=1;i<=sf;i++)
viz[st[i]]=1;
viz[st[1]]=0;
for(i=nr;i>=1;i--)
if(!viz[i])
{
while(sf>1 && semn(vp[st[sf-1]],vp[st[sf]],vp[i])<0)
sf--;
st[++sf]=i;
}
double arie=0;
for(i=1;i<sf;i++)
arie+=((double)vp[st[i]].x-vp[st[i+1]].x)
*(vp[st[i]].y+vp[st[i+1]].y)/2;
if(arie>0)
return arie;
return -arie;
}
int main ()
{
int i,j,k;
double s1,s2;
freopen("gradina.in","r",stdin);
freopen("gradina.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
v[i].y+=50000000;
v[i].ind=i;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
for(k=1;k<=n;k++)
if(k!=i && k!=j)
if(semn(v[i],v[j],v[k])<0)
p[k]=0;
else
p[k]=1;
p[i]=0;
p[j]=1;
s1=infas(0);
s2=infas(1);
s1-=s2;if(s1<0) s1=-s1;
for(k=1;k<=n;k++)
vecc[v[k].ind]=p[k];
if(s1==sol)
{
int schimb=0;
for(k=1;k<=n;k++)
if(p[k]<vecc[k])
{
schimb=1;
break;
}
else if(p[k]>vecc[k])
break;
if(schimb==1)
for(j=1;k<=n;k++)
p[k]=vecc[k];
}
if(s1<sol)
{
sol=s1;
for(k=1;k<=n;k++)
vec[v[k].ind]=p[k];
}
}
printf("%.1lf\n",sol);
for(i=1;i<=n;i++)
if(vec[i])
printf("V");
else
printf("I");
printf("\n");
return 0;
}