The first step towards solving this problem is finding a way to quickly compute the total income of a rectangular field. We will first describe a good solution to that subproblem.

It is possible to precompute in advance an ~N \times N~ matrix ~P~, where ~P[x][y]~ contains the sum of values in the rectangle with opposite corners in ~(0, 0)~ and ~(x, y)~. For the purposes of this problem, it is sufficient to calculate the matrix values with ~\mathcal O(N^4)~ time complexity, iterating over the whole rectangle for each matrix cell. Of course, it is possible to carry out the computation in ~\mathcal O(N^2)~, which is left as an exercise for the reader.

This precomputation is useful since we can then determine the total income of any rectangle in time ~\mathcal O(1)~ instead of ~\mathcal O(N^2)~ using the inclusion-exclusion formula:

$$\displaystyle sum(x_1, y_1, x_2, y_2) = P[x_2][y_2] - P[x_1-1][y_2] - P[x_2][y_1-1] + P[x_1-1][y_1-1]$$

A simple way of finding all valid rectangle pairs is trying out all possible quadruples of points as opposite corners of the two rectangles and checking whether they have the same sum using the formula above. This solution has a complexity of ~\mathcal O(N^8)~ and yields ~20\%~ of points.

The solution above can be easily optimized by iterating over triples instead of quadruples, immediately fixing the common vertex of the two rectangles. This reduces the complexity to ~\mathcal O(N^6)~ and yields ~40\%~ of points.

For the final optimization, we can exploit the fact that individual unit square incomes are restricted to the interval between ~-1000~ and ~1000~, which means that the total income of any rectangle falls between ~-1000N^2~ and ~1000N^2~. Since ~N~ is at most ~50~, we can use an array of size ~2000N^2~ to count the rectangles with each possible total income.

We will demonstrate the idea in the case of rectangles sharing the upper left and lower right corners, as in the picture. We first iterate over all possible common rectangle vertices. Then, for a fixed common vertex, we iterate over all possible upper left corners of rectangle 1 and use the array to track the number of rectangles 1 for each possible sum. After that, we iterate over all possible lower right corners of rectangle 2 and, for each rectangle 2 with a sum ~S~, look up the number of rectangles 1 with the same sum ~S~ and add that number to the solution. We repeat an equivalent procedure for rectangle pairs sharing the lower left and upper right corners.

The complexity of the algorithm described above is ~\mathcal O(N^4)~ and it is sufficient to score ~100\%~ of points.