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.

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[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
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
Codechef Long Challenge Solutions
February Long Challenge 2021
- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef
November Challenge 2020 SOLUTION CodeChef
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
October Lunchtime 2020 CodeChef SOLUTIONS
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP
RELATED :
- Top Best Keylogger in Python 3 Make One
- What is Hacking?
- Secrets of the Deep Dark Web
- CODECHEF September Lunchtime 2020 SOLUTIONS
- August Lunchtime 2020 SOLUTIONS
Related :
- A. Shandom Ruffle SOLUTION
- B. Pear TreaP SOLUTION
- C. Sneetches and Speeches 3 SOLUTION
- D. The Grim Treaper SOLUTION
- Y. Sneetches and Speeches 1 SOLUTION
- Z. Trick or Treap SOLUTION
- A. Floor Number SOLUTION CODE FORCES
- B. Symmetric Matrix SOLUTION CODE FORCES
- C. Increase and Copy SOLUTION CODE FORCES
- D. Non-zero Segments SOLUTION CODE FORCES
- E. Rock, Paper, Scissors SOLUTION CODE FORCES
- F. Number of Subsequences SOLUTION CODE FORCES
Related :
- Chef and Easy Queries SOLUTIONS CHEFEZQ
- Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE
- Positive AND SOLUTIONS POSAND
- Replace for X SOLUTIONS REPLESX
- Village Road Network SOLUTIONS VILLNET
- Random Knapsack SOLUTIONS RANDKNAP
- D-Dimensional MST SOLUTIONS DDIMMST
- Compress all Subsegments SOLUTIONS SEGCOMPR
- Adding Squares SOLUTIONS ADDSQURE
- Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE
- Rooted Minimum Spanning Tree SOLUTIONS ROOTMST