/* $Id$ */

/*

"Impachettamento rettangoli" (IOI 1995)
Copyright (C) 2000 Massimo Santini

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/

/* 
   Ci sono tre tipi di dati: i punti (x,y), i rettangoli (specificati
   da base e altezza (b,h)) e i rettangoli posizionati nel piano
   cartesiano, specificati da due punti (p,q) (quello in basso a sx e
   in alto a dx). Questi sono utilizzati per due strutture dati:
   l'insieme "in" dei rettangoli dati in ingresso e l'insieme dei
   rettangoli "sol" posizionati nel piano secondo la soluzione attuale.

   Si osservi che il programma non fornisce l'output richiesto. Manca
   la parte che raccolga le sole soluzioni di area minima e le stampi
   nel formato richiesto. Questo puņ essere ottenuto banalmente
   utiilizzando, ad esempio, delle liste.

*/

#include <stdio.h>

typedef struct s_point {
	int x, y;
} point; /* il tipo di dato "punto" */

typedef struct s_arect {
	int b, h;
} arect; /* il tipo di dato "rettangolo" */

typedef struct s_rect {
	point p, q;
} rect; /* il tipo di dato "rettangolo posizionato nel piano" */


/* massimo e minimo tra due numeri */

#define max(a,b) ( (a) > (b) ? (a) : (b) )
#define min(a,b) ( (a) < (b) ? (a) : (b) )

/* il confronto "minore" secondo l'odine parziale discusso */

#define lt(p,q)  ( (p).x < (q).x && (p).y < (q).y )

/* l'inclusione tra rettangoli */

#define rin(u,v) ( lt( sup( (u).p, (v).p ), inf( (u).q, (v).q ) ) )

/* stampa di un rettangolo posizionato nel piano */ 

#define printrect(u) printf( "[(%d,%d),(%d,%d)]", (u).p.x, (u).p.y, (u).q.x, (u).q.y  )
#define fprintrect(f,u) fprintf( (f), "[(%d,%d),(%d,%d)]", (u).p.x, (u).p.y, (u).q.x, (u).q.y  )

arect in[4]; /* la struttura dati che conserva l'input */
rect sol[4]; /* la struttura dati che conserva la soluzione */
int minarea; /* il valore corrente della minima area fin ora trovata */

/* calcolo del sup tra due punti */ 
point sup( point p, point q )
{
	point r;
	
	r.x = max( p.x, q.x );
	r.y = max( p.y, q.y );
	
	return r;
}

/* calcolo dell'inf tra due punti */ 
point inf( point p, point q )
{
	point r;
	
	r.x = min( p.x, q.x );
	r.y = min( p.y, q.y );
	
	return r;
}

/* 
   Questa procedura assume che in sol[k] per k <= l sia contenuta una
   soluzione parziale.

   Essa posiziona in sol[l+1] il rettangolo in[l+1] in tutte le
   posizioni possibili (lungo il perimetro dei rettangoli sol[k] con k
   <= l, e con la base e l'altezza scambiati se queste sono diverse).

   Quindi richiama la procedura "proc" che verifichera` che la
   soluzione parziale sol[k] con k <= l + 1 sia valida (si vedano
   test2, test3).

*/
void forall( int l, void (*proc)( void ) )
{
	int k; 
	int *px, *py, *qx, *qy;

	/* memorizzo dei puntatori agli elementi della struttura
	   da trattare per ragioni di efficienza e leggibilita`.
	   p(x,y) e q(x,y) sono i punti in basso a sx e in alto a dx
	   del rettangolo che viene aggiunto alla soluzione parziale.
	 */
	px = &(sol[l+1].p.x);
	py = &(sol[l+1].p.y);
	qx = &(sol[l+1].q.x);
	qy = &(sol[l+1].q.y);
	
	/* per tutti i rettangoli contenuti nella soluzione */
	for ( k=0; k<=l; k++ ) { 

		/*

		  Si parte con in[l+1] in basso a sx:

		              +--------+
		              |        |
		              | sol[k] |
				      |        |
		  +-----------q--------+
		  |           |
		  |  in[l+1]  |
		  |           |
		  p-----------+

		  e si finisce con in[l+1] in alto a dx:

		   	       +-----------q
		   	       |           |
		   	       |  in[l+1]  |
		     	   |           |
		  +--------p-----------+
	      |        |
	      | sol[k] |
	 	  |        |
		  +--------+

		 */
		
		
		*px = sol[k].p.x - in[l+1].b;
		*qx = sol[k].p.x;		
		do {
			*py = sol[k].p.y - in[l+1].h;
			*qy = sol[k].p.y;
			do {
				proc();
				(*py)++;
				(*qy)++;
			} while ( *py <=sol[k].q.y );
			(*px)++;
			(*qx)++;
		} while ( *px <= sol[k].q.x );
		
		/* se il rettangolo non e` quadrato, lo giro e faccio come sopra */
		if ( in[l+1].b != in [l+1].h ) {
			
			*px = sol[k].p.x - in[l+1].h;
			*qx = sol[k].p.x;		
			do {
				*py = sol[k].p.y - in[l+1].b;
				*qy = sol[k].p.y;
				do {
					proc();
					(*py)++;
					(*qy)++;
				} while ( *py <=sol[k].q.y );
				(*px)++;
				(*qx)++;
			} while ( *px <= sol[k].q.x );		   
		}

	}
}

void addsol( void ) 
{
	int a;
	rect br;
	arect abr;

	br.p = inf( inf( sol[0].p, sol[1].p ), inf( sol[2].p, sol[3].p ) );
	br.q = sup( sup( sol[0].q, sol[1].q ), sup( sol[2].q, sol[3].q ) );
	abr.b = br.q.x - br.p.x;
	abr.h = br.q.y - br.p.y;
	a = abr.b * abr.h ;
	
	if ( a <= minarea ) {
		minarea = a;
		printf( "A = %d, R = [%d, %d]\n", a, abr.b, abr.h );
	}
}

/* ritorna l'area che racchide i rettangoli sol[0], sol[1] e sol[2] */
int area2( void )
{
	rect br;

	br.p = inf( inf( sol[0].p, sol[1].p ), sol[2].p );
	br.q = sup( sup( sol[0].q, sol[1].q ), sol[2].q );
	return  (br.q.x - br.p.x) * (br.q.y - br.p.y);
}

/* ritorna l'area che racchide i rettangoli sol[0] e sol[1] */
int area1( void )
{
	rect br;

	br.p = inf( sol[0].p, sol[1].p );
	br.q = sup( sol[0].q, sol[1].q );
	return  (br.q.x - br.p.x) * (br.q.y - br.p.y);
}


/*

  Le procedure test1, test2 e test3 verificano che i rettangoli
  sin ora presenti non siano intersecanti e non superino l'area massima
  finora calcolata. Se questo e` il caso, procedono con forall a posizionare
  il successivo rettangolo.

*/

void test3( void )
{
	if ( rin( sol[0], sol[3] ) || 
		 rin( sol[1], sol[3] ) || 
		 rin( sol[2], sol[3] ) )
		return;
	else
		addsol();
}

void test2( void )
{
	if ( rin( sol[0], sol[2] ) || 
		 rin( sol[1], sol[2] ) ||
		 area2() > minarea )
		return;
	else
		forall( 2, test3 );
}

void test1( void )
{
	if ( rin( sol[0], sol[1] ) || 
		 area1() > minarea )
		return;
	else
		forall( 1, test2 );
}

/* legge il file d'ingresso in in[] */
void input( void )
{
	int i;
	
	for ( i=0; i<4; i++ )
		scanf( "%d %d\n", &(in[i].b), &(in[i].h) );
}

int main( void ) 
{
	input();

	/* calcola un limite superiore plausibile per l'area minima */
	minarea = min( 
		max( max( in[0].h, in[1].h ), max( in[2].h, in[3].h) )*
		(in[0].b + in[1].b + in[2].b + in[3].b),
		max( max( in[0].b, in[1].b ), max( in[2].b, in[3].b) )*
		(in[0].h + in[1].h + in[2].h + in[3].h) );

	/* posiziona il primo rettangolo */
	sol[0].p.x = 0;
	sol[0].p.y = 0;
	sol[0].q.x = in[0].b;
	sol[0].q.y = in[0].h;

	/* dispone in ogni modo possibile il primo...*/
	forall( 0, test1 );

	return 0;
}