# Minimum Dual Area DAREA SOLUTION

Page Contents

## Minimum Dual Area DAREA

Given NN points in a 2D2D space, find the minimum sum of areas of rectangles required to cover all the points given that we can use at most 22 non-overlapping rectangles whose sides can touch. The rectangles must be axis-aligned, meaning the sides are vertical and horizontal.

### Input

• The first line contains an integer TT, the number of test cases. Then the test cases follow.
• Each test case contains N+1N+1 lines of input.
• The first line contains a single integer NN, the number of points.
• The next NN lines each contains two integers xixi, yiyi, the coordinates of the ii-th point.

Note: Points need not be distinct.

### Output

For each test case, output in a single line the answer to the problem.

### Constraints

• 1≤T≤1051≤T≤105
• 1≤N≤1051≤N≤105
• 0≤xi,yi≤1090≤xi,yi≤109
• The sum of NN over all test cases is at most 105105.

Subtask #1 (100 points): original constraints

### Sample Input

``````3
1
100 100
4
1 100
100 100
100 1
1 1
5
1 100
100 100
100 1
1 1
50 50
``````

### Sample Output

``````0
0
4851
``````

### Explanation

Case 1: Since there is only one point, the minimum area of a rectangle to cover this point is 00.

Case 2: We can have rectangles as 22 opposite sides of the square. Since the width of the rectangles is 00, the total area is also 00.

Case 3: The optimal solution is with the rectangles having endpoints {(1,1),(100,1),(1,50),(100,50)}{(1,1),(100,1),(1,50),(100,50)} and {(1,100),(1,100),(100,100),(100,100)}{(1,100),(1,100),(100,100),(100,100)}. Therefore the total area is 49⋅99+0⋅99=485149⋅99+0⋅99=4851

Program:

``````from collections import defaultdict
def num():
return float("-inf")
def num2():
return float("inf")

def solve(p):
minium_X, maximum_X = defaultdict(num2), defaultdict(num)
minium_Y, maximum_Y = defaultdict(num2), defaultdict(num)
for x, y in p:
minium_X[y] = min(minium_X[y], x)
maximum_X[y] = max(maximum_X[y], x)

minium_Y[x] = min(minium_Y[x], y)
maximum_Y[x] = max(maximum_Y[x], y)

X = list(minium_Y.keys())
Y = list(minium_X.keys())
X.sort()
Y.sort()
area = num2()

pref, suff = [], []
mn, mx = num2(), num()

for x in X:
mn, mx = min(mn, minium_Y[x]), max(mx, maximum_Y[x])
pref.append((x - X) * (mx - mn))
mn, mx = num2(), num()
for x in X[-1::-1]:
mn, mx = min(mn, minium_Y[x]), max(mx, maximum_Y[x])
suff.append((X[0-1]-x) * (mx - mn))

suff = suff[-1::-1]
suff.append(0)
for i in range(len(X)):
area = min(area, pref[i-1+1] + suff[i+1])

pref, suff = [], []
mn, mx = num2(), num()

for y in Y:
mn, mx = min(mn, minium_X[y]), max(mx, maximum_X[y])
pref.append((y - Y) * (mx - mn))
mn, mx = num2(), num()
for y in Y[-1::-1]:
mn, mx = min(mn, minium_X[y]), max(mx, maximum_X[y])
suff.append((Y[-1]-y) * (mx - mn))
suff = suff[-1::-1]
suff.append(0)

for i in range(len(Y)):
area = min(area, pref[i] + suff[i+1])
return area

t = int(input())
for _ in range(t):
n = int(input())
p = []
for i in range(n):
li = list(map(int, input().split()))
p.append(li)
ans = solve(p)
print(ans)``````