← All solutions

Shortest judge solution: 1552 bytes. Shortest team solution (during contest): 1178 bytes.

Python solutions by the judges: only Pypy

First, observe that this is at heart a geometry problem. We are given a set of lower-left and upper-right vertices, and we’re asked for the area of the largest rectangle (with sides parallel to the axes) between some two chosen corners. One observation we make is that we can prune the input set. If there are two lower-left corners, (x₁, y₁) and (x₂, y₂), with x₁ ≤ x₂ and y₁ ≤ y₂, then we can remove (x₂, y₂) from the set. After this pruning, the set of lower-left corners forms a sequence L₁, L₂, L₃, . . . , L_n, with L_i = (x_i, y_i), and x_i < x_i+1, y_i > y_i+1. We can perform similar pruning on the upper-right corner set, getting the sequence U₁, U₂, . . . , U_m, with U_i = (p_i, q_i), and again p_i < p_i+1 and q_i > q_i+1.

We’ll cover two solutions to the problem. The first one is less geometric. Define u(i) to be the index of the optimum upper-right corner for L_i – that is, the rectangle L_i, U_u(i) has area no smaller than any other L_i, U_j. In the case of ties, choose the rightmost one. We’re claiming that u(i) is non-decreasing. A geometric proof is to draw out the picture, and notice that for any i < j, k < l, the sum of areas of L_i U_k and L_j U_l is larger than the sum of areas L_i U_l and L_j U_k. You can also just write out the areas and see the inequality holds.

This allows a divide-and-conquer solution. Take the middle of all the L_is, and find u(i) (through a linear scan). Then, for all j < i, we can consider only the upper right corners up to u(i), and for all the j > i we can consider only the upper corners starting from u(i), and recurse into both branches. Since we’re halving the set of Ls at each pass, we will have log n levels of branching, and in each of the levels each of the Us is getting considered only for one interval (with the exception of the boundaries, but these sum up to O(n log n) as well), so the runtime will be O((m + n) log n).

The other solution is geometric. For any two points U_i, U_j, let us consider the set of points L for which U_i gives a larger rectangle than U_j. The boundary of this set is a straight line, so the set of points L for which U_i is the best choice is an intersection of half-planes, i.e., a convex polygon which is possibly unbounded in some directions. The division of the plane into these polygons contains a total of O(n) vertices, and so we can run a sweep-line algorithm, with the events being a point from L appears, or the set of regions changes. This will run in O((m + n) log(m)) time.