Minimum Dual Area CodeChef Solution | DAREA

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 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 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.

Leave a Comment

Your email address will not be published.