Cod sursa(job #69175)

Utilizator VmanDuta Vlad Vman Data 1 iulie 2007 17:54:13
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.25 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define Nmax 256
#define infinit 100000000000000000LL
char marcaj[Nmax], marcaj2[Nmax];
int N, i, j, k, start,
    p1[Nmax], p2[Nmax], nr1, nr2, x[Nmax], y[Nmax];
long long s1, s2, mindif, aa, bb, 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);
}

void parametrii(int A,int B)
{
aa=y[A]-y[B];
bb=x[B]-x[A];
cc=x[A]*y[B]-x[B]*y[A];
}

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

void qsort1(int st, int dr)
{
int i,j,aux;
long long mx,my;
mx=x[p1[(st+dr)/2]]-x[start];
my=y[p1[(st+dr)/2]]-y[start];
i=st;
j=dr;
while (i<=j)
      {
      while ((x[p1[i]]-x[start])*my > mx*(y[p1[i]]-y[start])) ++i;
      while ((x[p1[j]]-x[start])*my < mx*(y[p1[j]]-y[start])) --j;
      if (i<=j)
         {
         aux=p1[i];
         p1[i]=p1[j];
         p1[j]=aux;
         ++i;
         --j;
         }
      }
if (i<dr) qsort1(i,dr);
if (j>st) qsort1(st,j);
}

void qsort2(int st, int dr)
{
int i,j,aux;
long long mx,my;
mx=x[p2[(st+dr)/2]]-x[start];
my=y[p2[(st+dr)/2]]-y[start];
i=st;
j=dr;
while (i<=j)
      {
      while ((x[p2[i]]-x[start])*my > mx*(y[p2[i]]-y[start])) ++i;
      while ((x[p2[j]]-x[start])*my < mx*(y[p2[j]]-y[start])) --j;
      if (i<=j)
         {
         aux=p2[i];
         p2[i]=p2[j];
         p2[j]=aux;
         ++i;
         --j;
         }
      }
if (i<dr) qsort2(i,dr);
if (j>st) qsort2(st,j);
}

int minim(int p[Nmax],int nr)
{
 int i,min;
 min=1;
 for (i=2;i<nr;++i)
      if ((y[p[i]]<y[p[min]])||((y[p[i]]==y[p[min]])&&(x[p[i]]<x[p[min]]))) min=i;
 return min;
}

int infasuratoare(int p[Nmax],int nr)
{
int st[Nmax],poz,i,s;
st[1]=p[1];
st[2]=p[2];
st[poz=3]=p[3];
for (i=4;i<=nr;++i)
    {
    st[++poz]=p[i];
    if (x[st[poz-2]]*y[st[poz-1]]+x[st[poz-1]]*y[st[poz]]+x[st[poz]]*y[st[poz-2]]
       -x[st[poz-2]]*y[st[poz]]-x[st[poz-1]]*y[st[poz-2]]-x[st[poz]]*y[st[poz-1]]<0)
       return 0;
    /*parametrii(st[poz-1],st[poz-2]);
    if (semn(st[poz])>0) return 0;//st[--poz]=p[i];*/
    }
s=0;
st[poz+1]=st[1];
for (i=1;i<=poz;++i)
    s+=x[st[i]]*y[st[i+1]]-x[st[i+1]]*y[st[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=0;i<N;++i)
    for (j=i+1;j<N;++j)
           {
           nr1=nr2=1;
           p1[nr1]=i;
           p2[nr2]=j;
           parametrii(i,j);
           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=minim(p1,nr1);
           p1[0]=p1[start];
           p1[start]=p1[1];
           p1[1]=p1[0];
           start=p1[0];
           //sort(p1+2,p1+nr1+1,cmp);
           qsort1(2,nr1);
           s1=infasuratoare(p1,nr1);
           if (s1==0) continue;
           //poligon 2
           start=minim(p2,nr2);
           p2[0]=p2[start];
           p2[start]=p2[1];
           p2[1]=p2[0];
           start=p2[0];
           //sort(p2+2,p2+nr2+1,cmp);
           qsort2(2,nr2);
           s2=infasuratoare(p2,nr2);
           if (s2==0) continue;
           verifica();

           //
           for (k=1;k<=nr1;++k)
               if (p1[k]==i) { p1[k]=j;break; }
           for (k=1;k<=nr2;++k)
               if (p2[k]==j) { p2[k]=i;break; }
           //poligon 1
           start=minim(p1,nr1);
           p1[0]=p1[start];
           p1[start]=p1[1];
           p1[1]=p1[0];
           start=p1[0];
           //sort(p1+2,p1+nr1+1,cmp);
           qsort1(2,nr1);
           s1=infasuratoare(p1,nr1);
           if (s1==0) continue;
           //poligon 2
           start=minim(p2,nr2);
           p2[0]=p2[start];
           p2[start]=p2[1];
           p2[1]=p2[0];
           start=p2[0];
           //sort(p2+2,p2+nr2+1,cmp);
           qsort2(2,nr2);
           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;
}