Rettangoli in Rettangoli

[bh3u4m]

Dati n rettangoli di base <b>b(n)</b> ed altezza <b>h(n)</b> trovare l\'area del più piccolo rettangolo che li possa contenere tutti al suo interno.
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: bh3u4m il 26-02-2004 01:00 ]

[Antimateria]

Suppongo che il rettangolo debba contenere i rettangolini senza che questi si sovrappongano... e questo rende il problema assolutamente improponibile! Non credo neanche che esista una formula semplice per scrivere quella funzione!!
<BR>
<BR>Propongo questo problema simile ma più facile, seppur interessante e non banale:
<BR>
<BR><!-- BBCode Start --><B>Dato un numero finito di rettangoli di nota base ed altezza, trovare il più piccolo rettangolo (ovvero quello di area più piccola) che possa contenere ciascuno dei rettangoli dati al suo interno.</B><!-- BBCode End -->
<BR>
<BR>Insomma, lo stesso problema di bh3u4m, ma con la possibilità di sovrapporre i rettangolini.[addsig]

[bh3u4m]

In questo caso basta prendere la base massima e l\'altezza massima.

[Antimateria]

No, no, no. Mi spiego:
<BR>Supponendo che per \"base di un rettangolo\" tu intenda il più lungo dei suoi lati, e per \"altezza\" il più corto, la tua soluzione va bene solo se i rettangolini devono essere disposti con i lati paralleli al rettangolone.
<BR>
<BR>Prendi questo esempio qua:
<BR>I rettangolini dati misurano 100x100 e 101x1. Allora, secondo la tua soluzione, il rettangolo minimo che li contiene misura 101x100. Ma invece si vede facilmente che il rettangolo 100x100 li contiene entrambi, perchè il secondo può essere sistemato sulla diagonale!
<BR>L\'ho detto che non era banale... <IMG SRC="images/forum/icons/icon_razz.gif"> [addsig]