#include <stdio.h>
#include <stdlib.h>
#include "draw.h"
#include "util.h"

#define DEITADO 0
#define DE_PE   1

#define CORTEVERT 0
#define CORTEHOR  1

// Variáveis globais
ponto l, w;             // lados do retângulo

/*
qtde *nRet;             // no paper está como v*(L)
                        // números de retângulos (l, w) que entram em um dado L

flag *solucao;          // no paper está como k*(L)
                        // indica a solução adotada
                        //  -1  -> não resolvido ainda
                        //   0  -> resolvido com packing homogêneo
                        // 1..7 -> resolvido usando a subdivisão B1,..,B7, respect.

ponto **ptoDiv;         // no paper está como i_k*(L)
                        // ponto de divisão, se usado alguma subdivisão,
                        //   i.e., k*(L) = {1,..,7}
*/

extern int *ptoDiv;
extern short *solNRet;

extern const int ptoDiv1;
extern const int ptoDiv2;
extern const int ptoDiv3;

extern const short nRet;
extern const short solucao; 
extern const short descSol;
extern const short descPtoDiv2;
extern const short descPtoDiv3;

// Variáveis locais
qtde ret;              // retangulos "desenhados"

ponto **ptoRet;         // solução em coordenadas dos retângulos
                        // ret[R] = ( Xesq, Yinf, Xdir, Ysup )
                        // coordenada inferior esquerda e superior direita do retângulo

flag corteR( ponto x, ponto y );
flag corteL( ponto *q );

void arruma( qtde id );

void normaliza( ponto *q );

void transladaX( qtde id, ponto deltaX );
void transladaY( qtde id, ponto deltaY );

void MakeFile( indice L, ponto *q );

void P1( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );
void P2( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );
void P3( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );
void P4( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );
void P5( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );
void P6( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );
void P7( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );
void P8( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY );

void DrawB1( indice L, ponto *q );
void DrawB2( indice L, ponto *q );
void DrawB3( indice L, ponto *q );
void DrawB4( indice L, ponto *q );
void DrawB5( indice L, ponto *q );
void DrawB6( indice L, ponto *q );
void DrawB7( indice L, ponto *q );

void DrawRetangulos( ponto x, ponto y );
void DrawR( indice L, ponto *q );
void Draw( indice L, ponto *q );

/**
 * Verifica se os retângulos serão desenhados em pés ou deitados
 * dentro do retângulo maior.
 */
flag corteR( ponto x, ponto y ) {
  qtde a, b;
  
  a = (x/l)*(y/w);
  b = (x/w)*(y/l);
  
  return (a>b) ? DEITADO : DE_PE ;
}

/**
 * Verifica como cortar um L, cortar na vertical ou na horizontal
 */
flag corteL( ponto *q ) {
  qtde a, b;
  
  // "quebra" o L em dois retângulos
  a = R_lim_inf( q[2], q[1] ) + R_lim_inf( q[0]-q[2], q[3] );
  b = R_lim_inf( q[2], q[1]-q[3] ) + R_lim_inf( q[0], q[3] );
  
  return (a>b) ? CORTEVERT : CORTEHOR;  
}

/**
 * Arruma as coordenadas de um retângulo
 */
void arruma( qtde id ) {

  if( ptoRet[id][0] > ptoRet[id][2] ) { SWAP( ptoRet[id][0], ptoRet[id][2] ); }
  if( ptoRet[id][1] > ptoRet[id][3] ) { SWAP( ptoRet[id][1], ptoRet[id][3] ); }
}

/**
 * Normaliza o L, só que não "deita" ele se estiver "de pé"
 */
void arrumaLdegenerado( ponto *q ) {

  // Estes cuatro son para eliminar retangulos "degenerados" pois
  // um retangulo sempre deve ser definido com q[0]=q[2] e q[1]=q[3].
  if( 0==q[2] ) { q[2]=q[0]; q[1]=q[3]; }
  else if( 0==q[3] ) { q[3]=q[1]; q[0]=q[2]; }
  else if ( q[2] == q[0] || q[3] == q[1] ) { q[2]=q[0]; q[3]=q[1]; }
}


/**
 * Translada o retângulo no eixo x
 */
void transladaX( qtde id, ponto deltaX ) {

  ptoRet[id][0] += deltaX;
  ptoRet[id][2] += deltaX;
}

/**
 * Translada o retângulo no eixo y
 */
void transladaY( qtde id, ponto deltaY ) {

  ptoRet[id][1] += deltaY;
  ptoRet[id][3] += deltaY;
}

/**
 * Deixa na posição certa, segundo P1
 */
void P1( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {

  qtde i;

  for( i=inicio; i<fim; i++ ) {
    ptoRet[i][1] = q[1]-ptoRet[i][1];
    ptoRet[i][3] = q[1]-ptoRet[i][3];

    arruma(i);

    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Deixa na posição certa, segundo P2
 */
void P2( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {
  
  qtde i;
  
  for( i=inicio; i<fim; i++ ) {
    ptoRet[i][0] = q[0]-ptoRet[i][0];
    ptoRet[i][2] = q[0]-ptoRet[i][2];

    arruma(i);

    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Deixa na posição certa, segundo P3
 */
void P3( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {
  
  qtde i;
  
  for( i=inicio; i<fim; i++ ) {
    ptoRet[i][0] = q[0]-ptoRet[i][0];
    ptoRet[i][2] = q[0]-ptoRet[i][2];

    ptoRet[i][1] = q[1]-ptoRet[i][1];
    ptoRet[i][3] = q[1]-ptoRet[i][3];

    arruma(i);

    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Deixa na posição certa, segundo P4
 */
void P4( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {
  
  qtde i;
  
  for( i=inicio; i<fim; i++ ) {
    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Deixa na posição certa, segundo P5
 */
void P5( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {
  
  qtde i;
  ponto tmp1, tmp2;

  for( i=inicio; i<fim; i++ ) {
    tmp1 = ptoRet[i][1];
    tmp2 = ptoRet[i][3];

    ptoRet[i][1] = q[0]-ptoRet[i][0];
    ptoRet[i][3] = q[0]-ptoRet[i][2];

    ptoRet[i][0] = tmp1;
    ptoRet[i][2] = tmp2;

    arruma(i);

    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Deixa na posição certa, segundo P6
 */
void P6( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {
  
  qtde i;
  ponto tmp1, tmp2;
  
  for( i=inicio; i<fim; i++ ) {
    tmp1 = ptoRet[i][0];
    tmp2 = ptoRet[i][2];

    ptoRet[i][0] = q[1]-ptoRet[i][1];
    ptoRet[i][2] = q[1]-ptoRet[i][3];

    ptoRet[i][1] = tmp1;
    ptoRet[i][3] = tmp2;

    arruma(i);

    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Deixa na posição certa, segundo P7
 */
void P7( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {
  
  qtde i;
  ponto tmp1, tmp2;

  for( i=inicio; i<fim; i++ ) {
    tmp1 = q[0]-ptoRet[i][0];
    tmp2 = q[0]-ptoRet[i][2];

    ptoRet[i][0] = q[1]-ptoRet[i][1];
    ptoRet[i][2] = q[1]-ptoRet[i][3];

    ptoRet[i][1] = tmp1;
    ptoRet[i][3] = tmp2;

    arruma(i);

    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Deixa na posição certa, segundo P8
 */
void P8( qtde inicio, qtde fim, indice L, ponto *q, ponto deltaX, ponto deltaY ) {
  
  qtde i;
  ponto tmp1, tmp2;

  for( i=inicio; i<fim; i++ ) {
    tmp1 = ptoRet[i][0];
    tmp2 = ptoRet[i][2];

    ptoRet[i][0] = ptoRet[i][1];
    ptoRet[i][2] = ptoRet[i][3];

    ptoRet[i][1] = tmp1;
    ptoRet[i][3] = tmp2;

    transladaX( i, deltaX );
    transladaY( i, deltaY );
  }
}

/**
 * Desenha em relação a subdivisão B1
 */
void DrawB1( indice L, ponto *q ) {
  indice L1, L2;
  ponto q1[4], q2[4], tmp[4];
  ponto largura, altura;
  ponto deltaX, deltaY;
  qtde inicio, fim;
  ponto div[2];

  div[0] = ptoDiv[L] & ptoDiv1;
  div[1] = (ptoDiv[L] & ptoDiv2) >> descPtoDiv2;
  posicaoPadraoB1( div, q, q1, q2 );

  // desenha L1
  tmp[0] = q1[0];
  tmp[1] = q1[1];
  tmp[2] = q1[2];
  tmp[3] = q1[3];
  arrumaLdegenerado( tmp );

  normalizar( q1 );
  L1 = q2i( q1[0], q1[1], q1[2], q1[3] );

  inicio = ret;
  DrawR( L1, q1 );
  fim = ret;
  
  deltaX = 0; deltaY = div[1];
  if( div[0] == 0 ) deltaY = q[3];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }

  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P8( inicio, fim, L1, q1, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P1( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P5( inicio, fim, L1, q1, deltaX, deltaY );
  }
  
  // desenha L2
  tmp[0] = q2[0];
  tmp[1] = q2[1];
  tmp[2] = q2[2];
  tmp[3] = q2[3];
  arrumaLdegenerado( tmp );

  normalizar( q2 );
  L2 = q2i( q2[0], q2[1], q2[2], q2[3] );

  inicio = ret;
  DrawR( L2, q2 );
  fim = ret;
  
  deltaX = 0; deltaY = 0;
  if( div[1]==0 ) deltaX = div[0];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }

  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P8( inicio, fim, L2, q2, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P2( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P6( inicio, fim, L2, q2, deltaX, deltaY );
  }
}

/**
 * Desenha em relação a subdivisão B2
 */
void DrawB2( indice L, ponto *q ) {
  indice L1, L2;
  ponto q1[4], q2[4], tmp[4];
  ponto largura, altura;
  ponto deltaX, deltaY;
  qtde inicio, fim;
  ponto div[3];

  div[0] = ptoDiv[L] & ptoDiv1;
  div[1] = (ptoDiv[L] & ptoDiv2) >> descPtoDiv2;
  posicaoPadraoB2( div, q, q1, q2 );

  // desenha L1
  tmp[0] = q1[0];
  tmp[1] = q1[1];
  tmp[2] = q1[2];
  tmp[3] = q1[3];
  arrumaLdegenerado( tmp );

  normalizar( q1 );
  L1 = q2i( q1[0], q1[1], q1[2], q1[3] );

  inicio = ret;
  DrawR( L1, q1 );
  fim = ret;

  deltaX = 0; deltaY = q[3];
  if( div[1]==q[1] ) deltaX = div[0];
  else if( tmp[0]==tmp[2] )  deltaY = div[1];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P8( inicio, fim, L1, q1, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P3( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P7( inicio, fim, L1, q1, deltaX, deltaY );
  }
  
  // desenha L2
  tmp[0] = q2[0];
  tmp[1] = q2[1];
  tmp[2] = q2[2];
  tmp[3] = q2[3];
  arrumaLdegenerado( tmp );

  normalizar( q2 );
  L2 = q2i( q2[0], q2[1], q2[2], q2[3] );

  inicio = ret;
  DrawR( L2, q2 );
  fim = ret;
  
  deltaX = 0; deltaY = 0;

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( largura>=altura ) P4( inicio, fim, L2, q2, deltaX, deltaY );
  else                  P8( inicio, fim, L2, q2, deltaX, deltaY );
}

/**
 * Desenha em relação a subdivisão B3
 */
void DrawB3( indice L, ponto *q ) {
  indice L1, L2;
  ponto q1[4], q2[4], tmp[4];
  ponto largura, altura;
  ponto deltaX, deltaY;
  qtde inicio, fim;
  ponto div[2];

  div[0] = ptoDiv[L] & ptoDiv1;
  div[1] = (ptoDiv[L] & ptoDiv2) >> descPtoDiv2;
  posicaoPadraoB3( div, q, q1, q2 );

  // desenha L1
  tmp[0] = q1[0];
  tmp[1] = q1[1];
  tmp[2] = q1[2];
  tmp[3] = q1[3];
  arrumaLdegenerado( tmp );

  normalizar( q1 );
  L1 = q2i( q1[0], q1[1], q1[2], q1[3] );

  inicio = ret;
  DrawR( L1, q1 );
  fim = ret;
  
  deltaX = 0; deltaY = 0;

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( largura>=altura ) P4( inicio, fim, L1, q1, deltaX, deltaY );
  else                  P8( inicio, fim, L1, q1, deltaX, deltaY );
  
  // desenha L2
  tmp[0] = q2[0];
  tmp[1] = q2[1];
  tmp[2] = q2[2];
  tmp[3] = q2[3];
  arrumaLdegenerado( tmp );

  normalizar( q2 );
  L2 = q2i( q2[0], q2[1], q2[2], q2[3] );

  inicio = ret;
  DrawR( L2, q2 );
  fim = ret;
  
  deltaX = div[0]; deltaY = div[1];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( largura>=altura ) P4( inicio, fim, L2, q2, deltaX, deltaY );
  else                  P8( inicio, fim, L2, q2, deltaX, deltaY );
}

/**
 * Desenha em relação a subdivisão B4
 */
void DrawB4( indice L, ponto *q ) {
  indice L1, L2;
  ponto q1[4], q2[4], tmp[4];
  ponto largura, altura;
  ponto deltaX, deltaY;
  qtde inicio, fim;
  ponto div[2];

  div[0] = ptoDiv[L] & ptoDiv1;
  div[1] = (ptoDiv[L] & ptoDiv2) >> descPtoDiv2;
  posicaoPadraoB4( div, q, q1, q2 );

  // desenha L1
  tmp[0] = q1[0];
  tmp[1] = q1[1];
  tmp[2] = q1[2];
  tmp[3] = q1[3];
  arrumaLdegenerado( tmp );

  normalizar( q1 );
  L1 = q2i( q1[0], q1[1], q1[2], q1[3] );

  inicio = ret;
  DrawR( L1, q1 );
  fim = ret;
  
  deltaX = 0; deltaY = 0;

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( largura>=altura ) P4( inicio, fim, L1, q1, deltaX, deltaY );
  else                  P8( inicio, fim, L1, q1, deltaX, deltaY );
  
  // desenha L2
  tmp[0] = q2[0];
  tmp[1] = q2[1];
  tmp[2] = q2[2];
  tmp[3] = q2[3];
  arrumaLdegenerado( tmp );

  normalizar( q2 );
  L2 = q2i( q2[0], q2[1], q2[2], q2[3] );

  inicio = ret;
  DrawR( L2, q2 );
  fim = ret;
  
  deltaX = q[3]; deltaY = 0;
  if( div[0]==q[0] ) deltaY = div[1];
  else if( tmp[0]==tmp[2] )  deltaX = div[0];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P8( inicio, fim, L2, q2, deltaX, deltaY );
  }
  else {
    if( largura>altura ) P3( inicio, fim, L2, q2, deltaX, deltaY );
    else                 P7( inicio, fim, L2, q2, deltaX, deltaY );
  }
}

/**
 * Desenha em relação a subdivisão B5
 */
void DrawB5( indice L, ponto *q ) {
  indice L1, L2;
  ponto q1[4], q2[4], tmp[4];
  ponto largura, altura;
  ponto deltaX, deltaY;
  qtde inicio, fim;
  ponto div[2];

  div[0] = ptoDiv[L] & ptoDiv1;
  div[1] = (ptoDiv[L] & ptoDiv2) >> descPtoDiv2;
  posicaoPadraoB5( div, q, q1, q2 );

  // desenha L1
  tmp[0] = q1[0];
  tmp[1] = q1[1];
  tmp[2] = q1[2];
  tmp[3] = q1[3];
  arrumaLdegenerado( tmp );

  normalizar( q1 );
  L1 = q2i( q1[0], q1[1], q1[2], q1[3] );

  inicio = ret;
  DrawR( L1, q1 );
  fim = ret;
  
  deltaX = 0; deltaY = 0;
  if( div[0]==0 ) deltaY = div[1];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P8( inicio, fim, L1, q1, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P1( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P5( inicio, fim, L1, q1, deltaX, deltaY );
  }
  
  // desenha L2
  tmp[0] = q2[0];
  tmp[1] = q2[1];
  tmp[2] = q2[2];
  tmp[3] = q2[3];
  arrumaLdegenerado( tmp );

  normalizar( q2 );
  L2 = q2i( q2[0], q2[1], q2[2], q2[3] );

  inicio = ret;
  DrawR( L2, q2 );
  fim = ret;
  
  deltaX = div[0]; deltaY = 0;
  if( div[1]==0) deltaX = q[2];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P8( inicio, fim, L2, q2, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P2( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P6( inicio, fim, L2, q2, deltaX, deltaY );
  }
}

/**
 * Desenha em relação a subdivisão B6
 */
void DrawB6( indice L, ponto *q ) {
  indice L1, L2;
  ponto q1[4], q2[4], tmp[4];
  ponto largura, altura;
  ponto deltaX, deltaY;
  qtde inicio, fim;
  ponto div[3];

  div[0] = ptoDiv[L] & ptoDiv1;
  div[1] = (ptoDiv[L] & ptoDiv2) >> descPtoDiv2;
  div[2] = (ptoDiv[L] & ptoDiv3) >> descPtoDiv3;
  posicaoPadraoB6( div, q, q1, q2 );

  // desenha L1
  tmp[0] = q1[0];
  tmp[1] = q1[1];
  tmp[2] = q1[2];
  tmp[3] = q1[3];
  arrumaLdegenerado( tmp );

  normalizar( q1 );
  L1 = q2i( q1[0], q1[1], q1[2], q1[3] );

  inicio = ret;
  DrawR( L1, q1 );
  fim = ret;
  
  deltaX = 0; deltaY = 0;
  if( div[0]==0 ) deltaY = div[1];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }

  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P8( inicio, fim, L1, q1, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P1( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P5( inicio, fim, L1, q1, deltaX, deltaY );
  }
  
  // desenha L2
  tmp[0] = q2[0];
  tmp[1] = q2[1];
  tmp[2] = q2[2];
  tmp[3] = q2[3];
  arrumaLdegenerado( tmp );

  normalizar( q2 );
  L2 = q2i( q2[0], q2[1], q2[2], q2[3] );

  inicio = ret;
  DrawR( L2, q2 );
  fim = ret;
  
  deltaX = div[0]; deltaY = 0;
  if( div[1]==0 ) deltaX = div[2];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }

  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P8( inicio, fim, L2, q2, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P2( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P6( inicio, fim, L2, q2, deltaX, deltaY );
  }
}

/**
 * Desenha em relação a subdivisão B7
 */
void DrawB7( indice L, ponto *q ) {
  indice L1, L2;
  ponto q1[4], q2[4], tmp[4];
  ponto largura, altura;
  ponto deltaX, deltaY;
  qtde inicio, fim;
  ponto div[3];

  div[0] = ptoDiv[L] & ptoDiv1;
  div[1] = (ptoDiv[L] & ptoDiv2) >> descPtoDiv2;
  div[2] = (ptoDiv[L] & ptoDiv3) >> descPtoDiv3;
  posicaoPadraoB7( div, q, q1, q2 );

  // desenha L1
  tmp[0] = q1[0];
  tmp[1] = q1[1];
  tmp[2] = q1[2];
  tmp[3] = q1[3];
  arrumaLdegenerado( tmp );

  normalizar( q1 );
  L1 = q2i( q1[0], q1[1], q1[2], q1[3] );

  inicio = ret;
  DrawR( L1, q1 );
  fim = ret;
  
  deltaX = 0; deltaY = div[1];
  if( div[0]==0 ) deltaY = div[2];
  
  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }
  
  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P8( inicio, fim, L1, q1, deltaX, deltaY );
  }
  else {
    if( largura>=altura ) P1( inicio, fim, L1, q1, deltaX, deltaY );
    else                  P5( inicio, fim, L1, q1, deltaX, deltaY );
  }
  
  // desenha L2
  tmp[0] = q2[0];
  tmp[1] = q2[1];
  tmp[2] = q2[2];
  tmp[3] = q2[3];
  arrumaLdegenerado( tmp );

  normalizar( q2 );
  L2 = q2i( q2[0], q2[1], q2[2], q2[3] );

  inicio = ret;
  DrawR( L2, q2 );
  fim = ret;
  
  deltaX = 0; deltaY = 0;
  if( div[1]==0 ) deltaX = div[0];

  if( tmp[0]!=tmp[1] ) { largura = tmp[0]; altura = tmp[1]; }
  else               { largura = tmp[2]; altura = tmp[3]; }

  if( tmp[0]==tmp[2] ) {
    if( largura>=altura ) P4( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P8( inicio, fim, L2, q2, deltaX, deltaY );
  }
  else {  
    if( largura>=altura ) P2( inicio, fim, L2, q2, deltaX, deltaY );
    else                  P6( inicio, fim, L2, q2, deltaX, deltaY );
  }
}

/**
 * Desenha os retângulos
 */
void DrawRetangulos( ponto x, ponto y ) {
  int i, j;

  flag corte = corteR( x, y );

  if( corte == DEITADO )
    for( i=0; i+l<=x; i+=l )
      for( j=0; j+w<=y; j+=w ) {
        ptoRet[ret][0] = i;
        ptoRet[ret][1] = j;
        ptoRet[ret][2] = i+l;
        ptoRet[ret][3] = j+w;
        ret++;
      }

  else
    for( i=0; i+w<=x; i+=w )
      for( j=0; j+l<=y; j+=l ) {
        ptoRet[ret][0] = i;
        ptoRet[ret][1] = j;
        ptoRet[ret][2] = i+w;
        ptoRet[ret][3] = j+l;
        ret++;
      }
}

/**
 * Função recursiva que desenha os retângulos
 */
void DrawR( indice L, ponto *q ) {
  int i;
  qtde inicio, fim;

  switch( (solNRet[L] & solucao) >> descSol ) {
  case HOMOGENEO:

    // L não degenerado
    if( q[0] != q[2] ) {

      flag corte = corteL( q );
      if( corte == CORTEVERT ) {
        DrawRetangulos( q[2], q[1] );
        inicio = ret;
        DrawRetangulos( fechaEmZ( q[0]-q[2] ), q[3] );
        fim = ret;
        for( i=inicio; i<fim; i++ )
          transladaX( i, q[2] );
      }
      else {
        inicio = ret;
        DrawRetangulos( q[2], fechaEmZ( q[1]-q[3] ) );
        fim = ret;
        for( i=inicio; i<fim; i++ )
          transladaY( i, q[3] );
        DrawRetangulos( q[0], q[3] );
      }
    }
    // L degenerado (R)
    else
      DrawRetangulos( q[0], q[1] );

    break;

  case B1:  DrawB1( L, q ); break;
  case B2:  DrawB2( L, q ); break;
  case B3:  DrawB3( L, q ); break;
  case B4:  DrawB4( L, q ); break;
  case B5:  DrawB5( L, q ); break;
  case B6:  DrawB6( L, q ); break;
  case B7:  DrawB7( L, q ); break;
  default:
    printf("solucao inexistente: %d\n", (solNRet[L] & solucao) >> descSol );
    exit(0);
    break;
  }

}

/**
 * Gera o arquivo com as soluções
 */
void MakeFile( indice L, ponto *q ){
  int i;
  qtde n;
  FILE *file;

  file = fopen( "solution.txt", "w" );
  if( file==NULL ) {
    printf("Erro ao abrir o arquivo solution.txt\n");
    exit(0);
  }

  n = solNRet[L] & nRet;

  fprintf( file, "%d %d %d\n", (int)n+1, (int)q[0], (int)q[1] );
  fprintf( file, "0 0 %d %d\n", (int)q[0], (int)q[1] );

  for( i=0; i<n; i++)
    fprintf( file, "%d %d %d %d\n", (int)ptoRet[i][0], (int)ptoRet[i][1], (int)ptoRet[i][2], (int)ptoRet[i][3] );


  fclose( file );
}

/**
 * Aloca o vetor ptoRet, chama DrawR e gera o arquivo
 */
void Draw( indice L, ponto *q ) {
  int i;
  qtde n;

  n = solNRet[L] & nRet;

  ptoRet = (ponto**) malloc( n*sizeof( ponto* ) );
  if( ptoRet == NULL ) {
    printf("\nErro de alocacao de memoria\n");
    exit(0);
  }
  for( i=0; i<n; i++ ) {
    ptoRet[i] = (ponto*) malloc( 4*sizeof( ponto ) );
    if( ptoRet[i] == NULL ) {
      printf("\nErro de alocacao de memoria\n");
      exit(0);
    }
  }

  ret = 0;

  DrawR( L, q );

  MakeFile( L, q );

  for( i=0; i<n; i++ )
    free( ptoRet[i] );
  free( ptoRet );
}