Cod sursa(job #69110)

Utilizator VmanDuta Vlad Vman Data 1 iulie 2007 12:05:31
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.8 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define Nmax 256
#define infinit 100000000000000000LL

int N, i, j, k, marcaj[Nmax], marcaj2[Nmax], start,
    p1[Nmax], p2[Nmax], nr1, nr2;
long long x[Nmax], y[Nmax], 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];
}

int semn(int A)
{
if (aa*x[A]+bb*y[A]+cc>0) return 1;
	return -1;
}

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

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

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];
    parametrii(st[poz-1],st[poz-2]);
    if (semn(st[poz])>0) st[--poz]=p[i];
    }
s=0;
st[poz+1]=st[1];
if (poz==nr) //arie
   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;
}

void cauta()
{
for (i=0;i<N;++i)
    for (j=0;j<N;++j)
        if (i!=j)
           {
           nr1=nr2=1;
           p1[nr1]=i;
           p2[nr2]=j;
           parametrii(i,j);
           for (k=0;k<N;++k)
               if ((k!=i)&&(k!=j)&&(semn(k)>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);
           qsort(p1,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);
           qsort(p2,2,nr2);
           s2=infasuratoare(p2,nr2);
           if (s2==0) continue;
           //diferenta?
           if (abs(s1-s2)<mindif)
              {
              mindif=abs(s1-s2);
              memset(marcaj,0,sizeof(marcaj));
              for (k=1;k<=nr1;++k)
                  marcaj[p1[k]]=1;
              }
              else
              if (abs(s1-s2)==mindif)
              {
              //verifica lexicografic
              memset(marcaj2,0,sizeof(marcaj));
              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(marcaj2,marcaj,sizeof(marcaj2));break; }
                     else if ((marcaj[k]==marcaj[0])&&(marcaj2[k]!=marcaj2[0])) break;
              }
           }
}

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;
}