Minimum Dual Area DAREA SOLUTION

by

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.

Subtasks

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.

Minimum Dual Area DAREA SOLUTION

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

Minimum Dual Area DAREA SOLUTION

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[0]) * (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[0]) * (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)

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :