title: Minimal area matrix covering
body: <p>Considering an n-by-n binary matrix, I would like to find the minimal area of two rectangles that would cover all the ones (1s). That is, the sum of the areas of the rectangles must be minimal.
  The rectangles can overlap.</p>
  
  <p>Example:</p>
  
  <pre><code>0 0 0 1 1 1 0 0 0
  0 0 0 1 1 1 0 0 0
  0 0 0 1 1 1 0 0 0
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  0 0 0 1 1 1 0 0 0
  0 0 0 1 1 1 0 0 0
  0 0 0 1 1 1 0 0 0
  </code></pre>
  
  <p>The minimal area is: <code>3 * 9 + 9 * 3 = 54</code></p>
  
  <p>I'm interested to know if there is a solution better than <code>O(n^4)</code>.</p>