Minimum Dual Area CodeChef Solution | Easy Approach

Share:
Minimum Dual Area CodeChef Solution

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

Minimum Dual Area CodeChef Solution

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pi 3.141592653589793238462643383279
#define mod 1e9+7
#define Fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pll pair<long long ,long long>
#define mk make_pair
#define psieve void sieve(){ memset(prime, true, sizeof(prime)); for(ll p=2; p*p<=maxn; p++) if (prime[p]) for (ll i=p*2; i<=maxn; i+= p) prime[i] = false; }
#define all(x) x.begin(),x.end()
#define sii set<in>
#define vec vector<long long>
#define f0(i,n) for(long long i=0;i<n;i++)
#define f1(i,n) for(long long i=1;i<=n;i++)
int main() 
{
Fastio
int t;
cin>>t;
while(t--)
{
 ll n;
 cin>>n;
 vector<pair<ll,ll>>x;
 vector<pair<ll,ll>>y;
 multiset<ll>X;
 multiset<ll>Y;
 for(ll i=0;i<n;i++)
 {
     ll l1,l2;
     cin>>l1>>l2;
     x.pb({l1,l2});
     y.pb({l2,l1});
     X.insert(l1);
     Y.insert(l2);

 }
 sort(x.begin(),x.end());
 sort(y.begin(),y.end());
 ll height1=0;
 ll height2=0;
 ll h1max=0;
 ll h1min=LONG_MAX;
 ll area=LONG_MAX;
 for(ll 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();
     ll newarea=(x[i].first-x[0].first)*height1+(x[n-1].first-x[i+1].first)*height2;
     area=min(area,newarea);
 }

 ll width1=0;
 ll width2=0;
 ll w1max=0;
 ll w1min=LONG_MAX;
 for(ll 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();
     ll 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;
}

Java

import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;

class DAREA {
	
	public static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader() {
            br = new BufferedReader(new
            InputStreamReader(System.in));
        }
 
        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static class Pair implements Comparable<Pair>{
    	int x;
    	int y;

    	Pair(int x, int y){
    		this.x = x;
    		this.y = y;
    	}

    	public int compareTo(Pair o){
    		if(this.x != o.x){
    			return this.x - o.x;
    		}else{
    			return this.y - o.y;
    		}
    	}
    }

	public static void main(String[] args) throws java.lang.Exception {
		FastReader scn = new FastReader();
		PrintWriter pw = new PrintWriter(System.out);
		int t = scn.nextInt();
		while(t-->0){
			int n = scn.nextInt();
			Pair[] list1 = new Pair[n];
            Pair[] list2 = new Pair[n];
			for(int i=0; i<n; i++){
				int x1 = scn.nextInt();
				int y1 = scn.nextInt();
				list1[i] = new Pair(x1, y1);
                list2[i] = new Pair(y1, x1);
			}
			if(n <= 2){
				pw.println(0);
			}else{
				Arrays.sort(list1);
				long ans1 = calculate(list1);
				Arrays.sort(list2);
				long ans2 = calculate(list2);
				pw.println(Math.min(ans1, ans2));
			}
		}
		pw.close();
	}

    public static long calculate(Pair[] list){
        int n = list.length;
        int[] prefmin = new int[n];
        int[] prefmax = new int[n];

        prefmax[0] = prefmin[0] = list[0].y;
        for(int i=1; i<n; i++){
            prefmax[i] = Math.max(prefmax[i-1], list[i].y);
            prefmin[i] = Math.min(prefmin[i-1], list[i].y);
        }

        long ans = (list[n - 1].x - list[0].x) * 1L * (prefmax[n - 1] - prefmin[n - 1]);
        int mini = list[n - 1].y, maxi = list[n - 1].y;
        for (int i = n - 2; i >= 0; i--) {
            ans = Math.min((prefmax[i] - prefmin[i]) * 1L * (list[i].x - list[0].x) + (maxi - mini) * 1l * (list[n - 1].x - list[i + 1].x), ans);
            mini = Math.min(list[i].y, mini);
            maxi = Math.max(list[i].y, maxi);
        }
        return ans;
    }
}

Python

from collections import defaultdict
def NINF():
    return float("-inf")
def INF():
    return float("inf")

def solve(p):
    minium_X, maximum_X = defaultdict(INF), defaultdict(NINF) ## at y
    minium_Y, maximum_Y = defaultdict(INF), defaultdict(NINF) ## at x
    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 = INF()

    ##----
    pref, suff = [], []
    mn, mx = INF(), NINF()
    ## solve vertical dp
    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 = INF(), NINF()
    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)
    ## FIND ANSWER FOR VERTICAL SEPARATION
    for i in range(len(X)):
        area = min(area, pref[i-1+1] + suff[i+1])

    ##----------------------------
    pref, suff = [], []
    mn, mx = INF(), NINF()
    ## solve horizontal dp
    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 = INF(), NINF()
    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)
    ## FIND ANSWER FOR VERTICAL SEPARATION
    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)

Minimum Dual Area CodeChef Solution

Read more post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x