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 : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
 
0111
0111
0111
0111
=> 
12
un seul rectangle [1,3] [0,3] = 3 * 4 = 12

Code : Sélectionner tout - Visualiser dans une fenêtre à part
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]