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
