Strange Covering
Contest: Codeforces Round 694 (Div. 1)
Difficulty rating: 3500
Tags: divide and conquer

You are given $$$n$$$ points on a plane.

Please find the minimum sum of areas of two axis-aligned rectangles, such that each point is contained in at least one of these rectangles.

Note that the chosen rectangles can be degenerate. Rectangle contains all the points that lie inside it or on its boundary.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$)  — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points.

The following $$$n$$$ lines contain the coordinates of the points $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$). It is guaranteed that the points are distinct.

It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case print one integer — the minimum sum of areas.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
In the first two test cases the answer consists of 2 degenerate rectangles. In the third test case one of the possible answers consists of two rectangles $$$1 \times 1$$$ with bottom left corners $$$(0,0)$$$ and $$$(9,9)$$$.

Example input:
3
2
9 1
1 6
2
8 10
0 7
4
0 0
1 1
9 9
10 10

Example output:
0
0
2

Editorial:
It is clear that there are only 3 structurally different ways to pick two rectangles optimally:
1. Two rectangles do not intersect:  In this case one can iterate over all horizontal / vertical lines, separating those rectangles, find the extremal points in both halfplanes, and pick the rectangles with corners in the extremal points.
2. Rectangles do intersect, forming a «cross»:  In this case note that for each of the rectangles at least two sides lie on the boundary of the bounding box of all points:  To find such rectangles efficiently, one can iterate over the right boundary of the «vertical» rectangle. Let $$$L_d$$$ — be the lowest $$$y$$$ coordinate of a point to the left of left boundary of the «vertical» rectangle, $$$L_u$$$ — the highest $$$y$$$ coordinate of a point to the left of the boundary of the «vertical» rectangle, and similarly $$$R_d$$$ — the lowest $$$y$$$-coordinate of a point to the right of the «vertical» rectangle, $$$R_u$$$ — the highest $$$y$$$-coordinate of a point to the right.We can assume that $$$R_u \geq L_u$$$ (this can be guaranteed by picking a prefix in our data structure that we will find later). On such a prefix where $$$L_d \geq R_d$$$ we need to choose the rightmost bound. What remains is a subrange where $$$L_d \leq R_d$$$ and $$$L_u \leq R_u$$$. If we fix two bounds of a rectangle $$$L$$$ and $$$R$$$, their total area equals $$$(R_u - L_d) \cdot H + (R-L) \cdot W$$$, where $$$W$$$ is the height of the bounding box, and $$$H$$$ — its length. Rewriting $$$(R_u - L_d) \cdot H + (R-L) \cdot W = (R \cdot W + R_u \cdot H) - (L \cdot W + L_d \cdot H)$$$ one can see that the optimal $$$L$$$ can be chosen with a segment tree.
3. Two rectangles intersect in a such a way so that one of the vertices lies inside or on the boundary of the other one:  In this case one of the corners of each rectangle coincides with a corner of the bounding box. Let's call such a corner interesting.   If we fix the interesting vertex of one of the rectangles, the remaining rectangle can be uniquely determined. Looking at the formulas, it is clear that once we know the $$$x$$$-coordinate of an interesting corner of the rectangles, one can choose the $$$y$$$-coordinate of the interesting corner by answering a query in form «minimize $$$a \cdot x+b \cdot y$$$», where $$$(a, b)$$$ — one of the pairs belonging to a fixed precomputed set, and $$$(x,y)$$$ is a query. Dividing the expression by $$$x$$$ one can get $$$a+b \cdot \frac{y}{x}$$$ — a standard query that can be solved using convex hull trick. The only piece remaining is to guarantee that the chosen rectangles intersect. To achieve this once we fixed $$$x$$$ we only need to consider a continuous segment of $$$y$$$s, so we need to find the maximal value of a subrange of linear functions, which can be implemented in offline manner in $$$O(n \log n)$$$ time with a segment tree of convex stacksThe overall complexity of this solution is $$$O(n \log n)$$$.