Cod sursa(job #213431)
Utilizator | Data | 9 octombrie 2008 19:55:54 | |
---|---|---|---|
Problema | Gradina | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 5.46 kb |
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
struct punct{int x; int y; int p;};
punct v[255], v1[255], v2[255], aux;
int n, i, j, st1[255], vf1, st2[255], vf2, nr1, nr2, k, ppi, ppj;
int a1, a2, rez, fb;
double finn;
int sol[255], fin[255], nr, x[255];
inline bool cmp(punct a, punct b)
{
if ((a.x<b.x)||((a.x==b.x)&&(a.y<b.y)))
return true;
else
return false;
}
inline int saxifuz(punct a, punct b, punct c)
{
return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - b.x*a.y - a.x*c.y;
}
bool bun(punct a, punct b, punct c){
if (a.x*b.y+b.x*c.y+c.x*a.y<=c.x*b.y+b.x*a.y+a.x*c.y)
return true;
else
return false;
}
int arie(punct vv[])
{
int a=0;
int i;
for (i=1;i<nr;i++)
a=a+vv[x[i]].x*vv[x[i+1]].y-vv[x[i+1]].x*vv[x[i]].y;
return abs(a);
}
void infasuratoare(punct v[], int &n, int st[], int &vf)
{
int i, j, s1[255], s2[255], v1, v2;
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
v1=v2=2;
s1[1]=1;
s1[2]=2;
for (i=3;i<=n;i++){
while ( (v1>1) && (saxifuz( v[s1[v1-1]], v[s1[v1]], v[i] ) >= 0 ) )
v1--;
v1++;
s1[v1]=i;
}
s2[1]=n;
s2[2]=n-1;
for (i=n-2;i>=1;i--){
while ( (saxifuz( v[s2[v2-1]], v[s2[v2]], v[i] ) >=0 ) && (v2>1) )
v2--;
v2++;
s2[v2]=i;
}
vf=0;
for (i=1; i<v1; i++){
vf++;
st[vf]=s1[i];
}
for (i=1; i<=v2; i++){
vf++;
st[vf]=s2[i];
}
}
bool mai_bun()
{
long i=1;
while ((sol[i]==fin[i])&&(i<=n))
i++;
if (sol[i]<fin[i])
return true;
else
return false;
}
void scula()
{
int k;
infasuratoare(v1, nr1, st1, vf1);
infasuratoare(v2, nr2, st2, vf2);
nr=vf1;
for (k=1;k<=nr;k++)
x[k]=st1[k];
a1=arie(v1);
nr=vf2;
for (k=1;k<=nr;k++)
x[k]=st2[k];
a2=arie(v2);
fb=abs(a1-a2);
if ((vf1-1)!=nr1||(vf2-1)!=nr2)
fb=1999999999;
if (fb==rez)
if (mai_bun())
for (k=1;k<=n;k++)
fin[k]=sol[k];
if (fb<rez)
{
rez=fb;
for (k=1;k<=n;k++)
fin[k]=sol[k];
}
}
int main(){
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].p=i;
}
rez=2000000000;
sort(v+1, v+n+1, cmp);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i!=j)
{
nr1=nr2=0;
sol[v[i].p]=1;
sol[v[j].p]=2;
for (k=1;k<=n;k++)
if (k!=i&&k!=j)
if (saxifuz(v[i], v[j], v[k])>0)
{
nr1++;
v1[nr1]=v[k];
sol[v[k].p]=1;
}
else
{
nr2++;
v2[nr2]=v[k];
sol[v[k].p]=2;
}
else
if (k==i)
{
nr1++;
v1[nr1]=v[k];
ppi=nr1;
}
else
{
nr2++;
v2[nr2]=v[k];
ppj=nr2;
}
if ((nr1>=3)&&(nr2>=3))
scula();
sol[v[i].p]=2;
sol[v[j].p]=1;
nr1=nr2=0;
nr1=nr2=0;
sol[v[i].p]=2;
sol[v[j].p]=1;
for (k=1;k<=n;k++)
if (k!=i&&k!=j)
if (saxifuz(v[i], v[j], v[k])>0)
{
nr1++;
v1[nr1]=v[k];
sol[v[k].p]=1;
}
else
{
nr2++;
v2[nr2]=v[k];
sol[v[k].p]=2;
}
else
if (k==i)
{
nr2++;
v2[nr2]=v[k];
}
else
{
nr1++;
v1[nr1]=v[k];
}
if (nr1>=3&&nr2>=3)
scula();
}
finn=1.0*rez/2;
printf("%.1lf\n",finn);
for (i=1;i<=n;i++)
if (fin[i]==1)
printf("I");
else
printf("V");
printf("\n");
return 0;
}