Enveloppement de points dans deux rectangles

Bonjour,

Quelqu'un peux m'aider avec un algorithme pour envelopper des points avec deux rectangles de superficie minime .

Les points sont représentés par des 1 dans une matrice N*N qui contient 1 et 0. Un rectangle peux avoir la superficie 0.

Dates d'entrée la matrice

Résultat : la somme minimale des superficies des deux rectangles

Code:

---

1 2 3 4 5 6 7

0111 0111 0111 0111 => 12

---

un seul rectangle [1,3] [0,3] = 3 * 4 = 12

Code:

---

1 2 3 4 5 6 7

0100 0100 0111 0110 => 8

---

avec 2 rectangles 2 + 2*3 [1,1][0,1] et [1,3][2,3]

Bonjour,

Je ne comprend pas bien comment tu défini un rectangle..
" un seul rectangle [2,5] [0,3] 4*3 = 12 "
pour le premier exemple.. peut tu être plus explicite?

Le deuxieme exemple n'est pas correct :oops:

Ce n'est pas une matrice n*n..

Code:

---

1 2 3 4 5 6 7

0111 0111 0111 0111 => 12

---

[1,3][0,3]= (3-1+1) * (3-0+1) = 3 *4 = 12

Il y'avait la posiblite d'utiliser les deuxieme rectangle mais ca change rien au resultat.

Les deux rectangles peuvent-ils se recouvrir partiellement ?

Citation:

---

Envoyé par Nebulix

Les deux rectangles peuvent-ils se recouvrir partiellement ?

---

Oui

La discussion peut etre ferme.