Cod sursa(job #69185)

Utilizator VmanDuta Vlad Vman Data 1 iulie 2007 19:28:23
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.13 kb
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define Nmax 256
#define infinit 100000000000000000LL
char marcaj[Nmax], marcaj2[Nmax], p1[Nmax], p2[Nmax];
int N, i, j, k, start, nr1, nr2, x[Nmax], y[Nmax], aa, bb;
long long s1, s2, mindif, cc;

void citire()
{
freopen("gradina.in","r",stdin);
scanf("%d",&N);
for (i=0;i<N;++i)
    scanf("%d %d",&x[i],&y[i]);
fclose(stdin);
}

bool cmp(int a,int b)
{
return ((x[a]-x[start])*(y[b]-y[start])>(x[b]-x[start])*(y[a]-y[start]));
}

int infasuratoare(char p[Nmax],int nr)
{
int i,s;
for (i=4;i<=nr;++i)
    {
    if (x[p[i-2]]*y[p[i-1]]+x[p[i-1]]*y[p[i]]+x[p[i]]*y[p[i-2]]
       -x[p[i-2]]*y[p[i]]-x[p[i-1]]*y[p[i-2]]-x[p[i]]*y[p[i-1]]<0)
       return 0;
    }
s=0;
p[nr+1]=p[1];
for (i=1;i<=nr;++i)
    s+=x[p[i]]*y[p[i+1]]-x[p[i+1]]*y[p[i]];
return s>0?s:-s;
}

long long modul(long long x)
{
return x>0?x:-x;
}

void verifica()
{
           //diferenta?
           if (modul(s1-s2)<mindif)
              {
              mindif=modul(s1-s2);
              memset(marcaj,0,sizeof(marcaj));
              for (k=1;k<=nr1;++k)
                  marcaj[p1[k]]=1;
              }
              else
              if (modul(s1-s2)==mindif)
              {
              //verifica lexicografic
              memset(marcaj2,0,sizeof(marcaj2));
              for (k=1;k<=nr1;++k)
                  marcaj2[p1[k]]=1;
              for (k=0;k<N;++k)
                  if ((marcaj[k]!=marcaj[0])&&(marcaj2[k]==marcaj2[0])) { memcpy(marcaj,marcaj2,sizeof(marcaj2));break; }
                     else if ((marcaj[k]==marcaj[0])&&(marcaj2[k]!=marcaj2[0])) break;
              }
}

void cauta()
{
for (i=N-2;i>=0;--i)
    for (j=i+1;j<N;++j)
           {
           nr1=nr2=1;
           p1[nr1]=i;
           p2[nr2]=j;
           aa=y[i]-y[j];
           bb=x[j]-x[i];
           cc=x[i]*y[j]-x[j]*y[i];
           for (k=0;k<N;++k)
               if ((k!=i)&&(k!=j)&&(aa*x[k]+bb*y[k]+cc>0)) p1[++nr1]=k;
                  else if ((k!=i)&&(k!=j)) p2[++nr2]=k;
           if ((nr1<3)||(nr2<3)) continue;
           //poligon 1
           start=1;
           for (k=2;k<nr1;++k)
                 if ((y[p1[k]]<y[p1[start]])||((y[p1[k]]==y[p1[start]])&&(x[p1[k]]<x[p1[start]]))) start=k;
           p1[0]=p1[start];
           p1[start]=p1[1];
           p1[1]=p1[0];
           start=p1[0];
           sort(p1+2,p1+nr1+1,cmp);
           s1=infasuratoare(p1,nr1);
           if (s1==0) continue;
           //poligon 2
           start=1;
           for (k=2;k<nr2;++k)
                 if ((y[p2[k]]<y[p2[start]])||((y[p2[k]]==y[p2[start]])&&(x[p2[k]]<x[p2[start]]))) start=k;
           p2[0]=p2[start];
           p2[start]=p2[1];
           p2[1]=p2[0];
           start=p2[0];
           sort(p2+2,p2+nr2+1,cmp);
           s2=infasuratoare(p2,nr2);
           if (s2==0) continue;
           verifica();
           //ivnersez (i,j)
           //poligon 1
           for (k=1;k<=nr1;++k)
               if (p1[k]==i) { p1[k]=j;break; }
           if ((y[j]<y[p1[1]])||((y[j]==y[p1[1]])&&(x[j]<=x[p1[1]])))
           {
            p1[0]=p1[k];
            p1[k]=p1[1];
            p1[1]=p1[0];
           }
           start=p1[0];
           sort(p1+2,p1+nr1+1,cmp);
           s1=infasuratoare(p1,nr1);
           if (s1==0) continue;
           //poligon 2
           for (k=1;k<=nr2;++k)
               if (p2[k]==j) { p2[k]=i;break; }
           if ((y[i]<y[p2[1]])||((y[i]==y[p2[1]])&&(x[i]<=x[p2[1]])))
           {
            p2[0]=p2[k];
            p2[k]=p2[1];
            p2[1]=p2[0];
           }
           start=p2[0];
           sort(p2+2,p2+nr2+1,cmp);
           s2=infasuratoare(p2,nr2);
           if (s2==0) continue;
           verifica();
           }
}

int main()
{
      citire();
      mindif=infinit;
      cauta();
      freopen("gradina.out","w",stdout);
      printf("%.1f\n",(float)mindif/2);
      for (i=0;i<N;++i)
          if (marcaj[i]==marcaj[0]) printf("%c",'I');
             else printf("%c",'V');
      fclose(stdout);
      return 0;
}