Codechef June Long Challenge 2021 Solution | Minimum Dual Area (DAREA) | AskTheCode
Problem:
Given N points in a 2D space, find the minimum sum of areas of rectangles required to cover all the points given that we can use at most 2 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 T, the number of test cases. Then the test cases follow.
Each test case contains N+1 lines of input.
The first line contains a single integer N, the number of points.
The next N lines each contains two integers xi, yi, the coordinates of the i-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≤10^5
1≤N≤10^5
0≤xi,yi≤10^9
The sum of N over all test cases is at most 10^5.
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 50Sample Output:
0
0
4851EXPLANATION:
Case 1: Since there is only one point, the minimum area of a rectangle to cover this point is 0.
Case 2: We can have rectangles as 2 opposite sides of the square. Since the width of the rectangles is 0, the total area is also 0.
Case 3: The optimal solution is with the rectangles having endpoints {(1,1),(100,1),(1,50),(100,50)} and {(1,100),(1,100),(100,100),(100,100)}. Therefore the total area is 49⋅99+0⋅99=4851
Code:
In Java :
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef{
private static FS sc = new FS();
private static class FS {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st=new StringTokenizer(br.readLine());
} catch (IOException e) {}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
static long ans;
static int n;
public static void main(String[] args) {
int t = sc.nextInt();
StringBuilder str = new StringBuilder();
while(t-- > 0) {
ans = Long.MAX_VALUE;
n = sc.nextInt();
int[][] px = new int[n][2];
int[][] py = new int[n][2];
for(int i = 0; i < n; i++) {
px[i][0] = py[i][1] = sc.nextInt();
px[i][1] = py[i][0] = sc.nextInt();
}
solve(px);
solve(py);
str.append(ans == Long.MAX_VALUE ? "0\n":ans + "\n");
}
System.out.println(str);
}
static void solve(int[][] temp) {
int[][] p = new int[n][2];
for(int i = 0; i < n; i++) for(int j = 0; j < 2; j++) p[i][j] = temp[i][j];
Arrays.sort(p, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
long[] l = new long[n];
long[] r = new long[n];
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
Arrays.fill(l, Long.MAX_VALUE);
Arrays.fill(r, Long.MAX_VALUE);
for(int i = 0; i < n-1; i++) {
int x = p[i][0]-p[0][0];
min = Math.min(min, p[i][1]);
max = Math.max(max, p[i][1]);
long ans = x*1L*(max-min);
l[i] = ans;
}
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
for(int i = n-1; i > 0; i--) {
int x = p[n-1][0]-p[i][0];
min = Math.min(min, p[i][1]);
max = Math.max(max, p[i][1]);
long ans = x*1L*(max-min);
r[i] = ans;
}
for(int i = 0; i < n-1; i++) ans = Math.min(l[i]+r[i+1], ans);
}
}
In Python :
try:
import sys
from sys import stdin
def indx(li, val):
f, l, ind = 0, len(li), -1
while (f <= l) and (ind == -1):
mid = (f + l) // 2
if li[mid] == val:
ind = mid
else:
if val < li[mid]:
l = mid - 1
else:
f = mid + 1
return ind
def solveA(x, Y, ar, n):
max_h, min_h = 0, sys.maxsize
for i in range(n - 1):
max_h, min_h = max(x[i][1], max_h), min(x[i][1], min_h)
d1 = max_h - min_h
ind = indx(Y, x[i][1])
del Y[ind]
d2 = Y[-1] - Y[0]
new_ar = d1 * (x[i][0] - x[0][0]) + d2 * (x[n - 1][0] - x[i + 1][0])
ar = min(ar, new_ar)
return ar
def solveB(y, X, ar, n):
max_wd, min_wd = 0, sys.maxsize
for i in range(n - 1):
max_wd, min_wd = max(y[i][1], max_wd), min(y[i][1], min_wd)
d3 = max_wd - min_wd
ind = indx(X, y[i][1])
del X[ind]
d4 = X[-1] - X[0]
new_ar = d3 * (y[i][0] - y[0][0]) + d4 * (y[n - 1][0] - y[i + 1][0])
ar = min(ar, new_ar)
return ar
def solve(n):
x, y, X, Y, ar = [], [], [], [], sys.maxsize
for i in range(n):
a, b = map(int, sys.stdin.readline().split())
x.append([a, b]), y.append([b, a]), X.append(a), Y.append(b)
x.sort()
y.sort()
X.sort()
Y.sort()
re = solveA(x, Y, ar, n)
result = solveB(y, X, re, n)
if n == 1:
print(0)
else:
print(result)
def main():
for _ in range(int(sys.stdin.readline())):
n = int(sys.stdin.readline())
solve(n)
main()
except Exception:
pass
תגובות