#P1470F. Strange Covering
-
ID: 5738
Type: RemoteJudge
6000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Strange Covering
No submission language available for this problem.
Description
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.
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$.
For each test case print one integer — the minimum sum of areas.
Input
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
For each test case print one integer — the minimum sum of areas.
Samples
3
2
9 1
1 6
2
8 10
0 7
4
0 0
1 1
9 9
10 10
0
0
2
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)$.