Discussion :

[cyberkamikaz]

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]

[davly]

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?

[cyberkamikaz]

Le deuxieme exemple n'est pas correct

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Nebulix]

Les deux rectangles peuvent-ils se recouvrir partiellement ?

[cyberkamikaz]

Les deux rectangles peuvent-ils se recouvrir partiellement ?

Oui

[cyberkamikaz]

La discussion peut etre ferme.