Hello coders, today we are going to solve Minimum Dual Area CodeChef Solution in C++, Java and Python.
Task
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 Format
- 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 Format
For each test case, output in a single line the answer to the problem.
Constraints
- 1≤T≤105
- 1≤N≤105
- 0≤xi,yi≤109
- The sum of N over all test cases is at most 105
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 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
Solution – Minimum Dual Area CodeChef Solution
C++
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main() {
ios_base::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<pair<int, int>> x;
vector<pair<int, int>> y;
multiset<int> X;
multiset<int> Y;
for (int i = 0; i < n; ++i)
{
int a, b;
cin >> a >> b;
x.push_back({a, b});
y.push_back({b, a});
X.insert(a);
Y.insert(b);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
int height1 = 0;
int height2 = 0;
int h1Max = 0;
int h1Min = LONG_MAX;
int area = LONG_MAX;
for (int i = 0; i < n - 1; ++i)
{
h1Max = max(h1Max, x[i].second);
h1Min = min(h1Min, x[i].second);
height1 = h1Max - h1Min;
auto it = Y.find(x[i].second);
Y.erase(it);
height2 = *Y.rbegin() - *Y.begin();
int newArea = (x[i].first - x[0].first) * height1 +
(x[n - 1].first - x[i + 1].first) * height2;
area = min(area, newArea);
}
int width1 = 0;
int width2 = 0;
int w1Max = 0;
int w1Min = LONG_MAX;
for (int i = 0; i < n - 1; ++i)
{
w1Max = max(w1Max, y[i].second);
w1Min = min(w1Min, y[i].second);
width1 = w1Max - w1Min;
auto it = X.find(y[i].second);
X.erase(it);
width2 = *X.rbegin() - *X.begin();
int newArea = (y[i].first - y[0].first) * width1 +
(y[n - 1].first - y[i + 1].first) * width2;
area = min(area, newArea);
}
if (area == LONG_MAX)
area = 0;
cout << area << endl;
}
return 0;
}
Python
def area(rectangle):
[A,B] = rectangle
return abs(B[0] - A[0]) * abs(B[1] - A[1])
def solve(points):
if len(points)<=2:
return 0
points_x = sorted(points, key = lambda x: x[0])
ymx = {}
for p in points_x:
if p[0] not in ymx:
ymx[p[0]] = [p[1], p[1]]
continue
if p[1] < ymx[p[0]][0]:
ymx[p[0]][0] = p[1]
elif p[1] > ymx[p[0]][1]:
ymx[p[0]][1] = p[1]
y_right = {points_x[-1][0]: ymx[points_x[-1][0]]}
for i in range(N-2,-1, -1):
y_right[points_x[i][0]] = [min(y_right[points_x[i+1][0]][0], ymx[points_x[i][0]][0]),
max(y_right[points_x[i+1][0]][1], ymx[points_x[i][0]][1])]
r1_x = [points_x[0][0],points_x[0][0]]
r2_x = [points_x[-1][0], points_x[-1][0]]
r1_y = [ymx[points_x[0][0]][0],ymx[points_x[0][0]][1]]
r2_y = [y_right[points_x[-1][0]][0],y_right[points_x[-1][0]][1]]
area_max = float('inf')
for i in range(N-1):
r1_x[1] = points_x[i][0]
r2_x[0] = points_x[i+1][0]
if r1_y[0] > ymx[points_x[i][0]][0]:
r1_y[0] = ymx[points_x[i][0]][0]
if r1_y[1] < ymx[points_x[i][0]][1]:
r1_y[1] = ymx[points_x[i][0]][1]
r2_y = y_right[points_x[i+1][0]]
new_area = area([[r1_x[0],r1_y[0]],[r1_x[1],r1_y[1]]]) + area([[r2_x[0],r2_y[0]],[r2_x[1],r2_y[1]]])
if new_area < area_max:
area_max = new_area
points = [[y,x] for [x,y] in points]
points_x = sorted(points, key = lambda x: x[0])
ymx = {}
for p in points_x:
if p[0] not in ymx:
ymx[p[0]] = [p[1], p[1]]
continue
if p[1] < ymx[p[0]][0]:
ymx[p[0]][0] = p[1]
elif p[1] > ymx[p[0]][1]:
ymx[p[0]][1] = p[1]
y_right = {points_x[-1][0]: ymx[points_x[-1][0]]}
for i in range(N-2,-1, -1):
y_right[points_x[i][0]] = [min(y_right[points_x[i+1][0]][0], ymx[points_x[i][0]][0]),
max(y_right[points_x[i+1][0]][1], ymx[points_x[i][0]][1])]
r1_x = [points_x[0][0],points_x[0][0]]
r2_x = [points_x[-1][0], points_x[-1][0]]
r1_y = [ymx[points_x[0][0]][0],ymx[points_x[0][0]][1]]
r2_y = [y_right[points_x[-1][0]][0],y_right[points_x[-1][0]][1]]
full_rect = [[points_x[0][0], y_right[points[0][0]][0]], [points_x[-1][0],y_right[points[0][0]][1]]]
for i in range(N-1):
r1_x[1] = points_x[i][0]
r2_x[0] = points_x[i+1][0]
if r1_y[0] > ymx[points_x[i][0]][0]:
r1_y[0] = ymx[points_x[i][0]][0]
if r1_y[1] < ymx[points_x[i][0]][1]:
r1_y[1] = ymx[points_x[i][0]][1]
r2_y = y_right[points_x[i+1][0]]
new_area = area([[r1_x[0],r1_y[0]],[r1_x[1],r1_y[1]]]) + area([[r2_x[0],r2_y[0]],[r2_x[1],r2_y[1]]])
if new_area < area_max:
area_max = new_area
return area_max
for _ in range(int(input())):
N = int(input())
points = [[int(x) for x in input().split()] for i in range(N)]
print(solve(points))
Java
import java.io.*;
import java.util.*;
class Point{
public long x;
public long y;
}
public class Main {
static void print(ArrayList<Long> x)
{
return;
}
static class Reader {
static BufferedReader reader;
static StringTokenizer tokenizer;
/** call this method to initialize reader for InputStream */
static void init(InputStream input) {
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
/** get next word */
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
// TODO add check for eof if necessary
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static String nextLine() throws IOException {
return reader.readLine();
}
static long nextLong() throws IOException {
return Long.parseLong(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
public static void main(String[] args) throws IOException {
Reader.init(System.in);
int t = Reader.nextInt();
while(t-- > 0) {
solve();
}
}
public static void solve() throws IOException {
int N = Reader.nextInt();
Point point[] = new Point[N];
long x,y;
for(int i = 0 ; i < N ; i++) {
x = Reader.nextInt();
y = Reader.nextInt();
point[i] = new Point();
point[i].x=x;
point[i].y=y;
}
HashMap<Long, Long> mnX = new HashMap<>();
HashMap<Long , Long> mxX = new HashMap<>();
HashMap<Long , Long> mnY = new HashMap<>();
HashMap<Long , Long> mxY = new HashMap<>();
for(Point p : point) {
if(!(mnY.containsKey(p.x) || mxY.containsKey(p.x))) {
mnY.put(p.x , p.y);
mxY.put(p.x , p.y);
}
else {
mnY.put(p.x, Math.min(p.y, mnY.get(p.x)));
mxY.put(p.x, Math.max(p.y, mxY.get(p.x)));
}
if(!(mnX.containsKey(p.y) || mxX.containsKey(p.y))) {
mnX.put(p.y , p.x);
mxX.put(p.y , p.x);
}
else {
mnX.put(p.y, Math.min(p.x, mnX.get(p.y)));
mxX.put(p.y, Math.max(p.x, mxX.get(p.y)));
}
}
ArrayList<Long> x_cord = new ArrayList<>();
ArrayList<Long> y_cord = new ArrayList<>();
for(long key : mxX.keySet()) {
y_cord.add(key);
print(y_cord);
}
for(long key : mxY.keySet()) {
x_cord.add(key);
print(x_cord);
}
Collections.sort(x_cord);
Long bottom_y = Long.MAX_VALUE;
Long top_y = Long.MIN_VALUE;
print(x_cord);
Long left_most_x = x_cord.get(0);
Long ar_reg;
ArrayList<Long> lf_sm = new ArrayList<>();
ArrayList<Long> right_area=new ArrayList<>();
right_area.add(x_cord.get(0)*y_cord.get(0));
for(Long curr_x: x_cord) {
top_y = Math.max(top_y , mxY.get(curr_x));
bottom_y = Math.min(bottom_y, mnY.get(curr_x));
Long t1=top_y-bottom_y;
Long t2=curr_x - left_most_x;
right_area.add(y_cord.get(0)*x_cord.get(0));
ar_reg = Math.abs(t1*t2);
lf_sm.add(ar_reg);
}
ArrayList<Long> rg_sm = new ArrayList<>();
ArrayList<Long> left_area=new ArrayList<>();
bottom_y = Long.MAX_VALUE;
top_y = Long.MIN_VALUE;
left_area.add(x_cord.get(0)*y_cord.get(0));
left_most_x = x_cord.get(x_cord.size() - 1);
int nik = x_cord.size()- 1;
while(nik>=0)
{
Long curr_x = x_cord.get(nik);
bottom_y = Math.min(bottom_y, mnY.get(curr_x));
top_y = Math.max(top_y, mxY.get(curr_x));
Long t3=top_y-bottom_y;
Long t4=curr_x - left_most_x;
ar_reg = Math.abs(t3*t4);
rg_sm.add(ar_reg);
nik--;
}
int x_len = x_cord.size();
Long mnDualAr = Long.MAX_VALUE;
int l=0;
while( l < x_len){
int j = x_len - l - 2;
if(j<0)
{
j=0;
}
Long curr_area = lf_sm.get(l) + rg_sm.get(j);
mnDualAr = Math.min(mnDualAr, curr_area);
l++;
}
Collections.sort(y_cord);
lf_sm = new ArrayList<>();
rg_sm = new ArrayList<>();
Long left_x = Long.MAX_VALUE;
Long right_x = Long.MIN_VALUE;
//Collections.sort(y_cord);
Long bottom_most_y = y_cord.get(0);
for(Long curr_y : y_cord) {
//print(lf_sm);
left_x = Math.min(left_x, mnX.get(curr_y));
right_x = Math.max(right_x, mxX.get(curr_y));
Long t5=right_x-left_x;
Long t6=bottom_most_y - curr_y;
ar_reg = Math.abs(t5*t6);
lf_sm.add(ar_reg);
Long temp3=lf_sm.get(0);
Long y3=lf_sm.get(0);
}
left_x = Long.MAX_VALUE;
right_x = Long.MIN_VALUE;
bottom_most_y = y_cord.get(y_cord.size() - 1);
for(int i = y_cord.size()- 1 ; i>=0 ; i--) {
Long curr_y = y_cord.get(i);
//print(y_cord);
left_x = Math.min(left_x, mnX.get(curr_y));
right_x = Math.max(right_x, mxX.get(curr_y));
Long t7=right_x-left_x;
Long t8=curr_y - bottom_most_y;
ar_reg = Math.abs(t7*t8);
rg_sm.add(ar_reg);
Long temp2=rg_sm.get(0);
Long y2=lf_sm.get(0);
}
int y_len = y_cord.size();
for(int i = 0 ; i < y_len ; i++) {
int j = y_len - i - 2;
if(j<0)
j = 0;
Long curr_area = lf_sm.get(i) + rg_sm.get(j);
Long t1=rg_sm.get(0);
Long t2=lf_sm.get(0);
Long min_t=Math.min(t1,t2);
mnDualAr = Math.min(mnDualAr, curr_area);
}
System.out.println(mnDualAr);
}
}
Disclaimer: The above Problem (Minimum Dual Area) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.