Help Me Grow Carrots
An odd fellow recently became the mayor of the city. He wants to build a large rectangular carrot farm.
However, a large number of points in the city are already occupied with annoying stuff like apartments, clubs, and shopping malls. We need to find the largest contiguous rectangular plot in the city which is empty.
Assuming the entire city to be of \(10^6\) blocks, numbered from 0 to 999 in both dimensions, these are the coordinates of the obstacles. What is the area of the largest carrot farm that can be built, i.e, the largest empty submatrix?