PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
PROBLEM
Given N points in two-dimensional space, consider selecting up to two Non-Overlapping
rectangles such that each point is included in at least 1 rectangle, and the sum of areas of chosen rectangles is minimum. Determine this minimum sum of areas.
QUICK EXPLANATION
- Since the rectangles are non-overlapping, It is always possible to draw either a horizontal or a vertical line dividing the plane into two parts such that exactly one rectangle is on each side of the dividing line, covering all points on that side.
- Considering all candidates for such line, we can compute using prefix and suffix arras the areas of rectangles covering points on each side of the line and take minimum.
EXPLANATION
Minimum area of 1 rectangle to cover all points?
Let P be the set of points.
It is easy to see that the minimum area rectangle shall have the lower-left corner at (x1, y1) where x1 and y1 are the minimum x and y coordinates among points in P. Similarly, the upper right corner of such rectangle shall be at point (x2, y2) where x2 and y2 are the maximum values of x and y coordinates among points in P.
Let’s denote f(P) as the minimum area of one rectangle covering all points in P, given by (x2-x1)*(y2-y1).
What’s so special about Non-Overlapping rectangles
Claim: For every two non-overlapping rectangles, there exists either a horizontal or a vertical line.
Proof: Let’s assume that the first rectangle is represented by lower-left corner (x1, y1) and upper-right corner (x2, y2), and second rectangle is represented by lower-left corner (x3, y3) and upper-right corner (x4, y4).
It is easy to see that the area of overlap of these two rectangles is given by max(0, min(x2, x4)-max(x1,x3)) * max(0, min(y2, y4)-max(y1, y3))). Since these two rectangles are non-overlapping, this area must be 0, so there are two possibilities.
-
min(x2, x4)-max(x1,x3) \leq 0
Since x1 \leq x2 and x3 \leq x4, Either x2 \leq x3 or x4 \leq x1 possible.- if x2 <= x3, vertical line drawn at any x in range [x2, x3] divides the plane into two parts with 1 rectangle on each side.
- if x4 <= x1, vertical line drawn at any x in range [x4, x1] divides the plane into two parts with 1 rectangle on each side.
-
min(y2, y4)-max(y1,y3) \leq 0, Either y2 \leq y3 or y4 \leq y1 is possible.
- if y2 <= y3, horizontal line drawn at any y in range [x2, x3] divides the plane into two parts with 1 rectangle on each side.
- if y4 <= y1, horizontal line drawn at any y in range [y4, y1] divides the plane into two parts with 1 rectangle on each side.
Hence, for non-overlapping rectangles, there’s always a dividing line.
Reducing the choices for dividing lines
Since there’s a dividing line, we can see that all points on one side will be covered by one rectangle. We know how to calculate the area of such a rectangle, if we know the minimum and maximum X and Y coordinates of all points on one side of the line.
Claim: We only need to consider those values as candidates for the position of the dividing line, which appear as coordinates of at least 1 point.
Proof: Let’s assume we choose a vertical dividing line at x = a where a doesn’t appear as x-coordinate of any point. Since the sum of areas needs to be minimum, we can see that None of the rectangles would cover any point at line x = a, so we can move the dividing line to either direction till it reaches the x-coordinate of a point, say b. So x = b also works as a dividing line. Hence, by trying line x = b as a dividing line, we don’t need to test any line x = a if a doesn’t appear as x-coordinate of some line.
Hence, we only need to try those positions as dividing lines, which appear as x-coordinate or y-coordinate of some point in a given set P.
Minimum area of two non-overlapping rectangles
Now, we can try each value of a dividing line, which appears as a coordinate of some point. There are O(N) choices.
Let’s assume there’s a vertical dividing line x = a, the horizontal case is similar.
This line splits the original point set P into two sets P_1 and P_2 such that P_1 contains points with x-coordinate strictly smaller than a, and P_2 contains points with x-coordinate greater than or equal to a. We need to find value of f(P_1)+f(P_2) for these sets.
If we build the sets and compute f(P_1) and f(P_2) in O(N), the whole solution works in O(N^2) time which is sufficient for the first subtask, but not second.
Optimization
Let’s sort points by their x-coordinates, stored in a list L. Then if we consider a dividing line at x = a, some prefix of list L are the points present in P_1 and remaining suffix in P_2. Say |P_1| = A and |P_2| = B
Now we need to compute f(P_1) and f(P_2) for which we need to compute minimum and maximum values of x and y coordinates in both P_1 and P_2. x-coordinates are easy since the list of points is sorted by x-coordinate. We can take the x-coordinates of the first and last element in P_1 and P_2 as the minimum and maximum values of the x-coordinate.
For Y coordinate, for set P_1 we have to compute the minimum and maximum value of y-coordinate among the first A points, which can be done using prefix minimum and prefix maximum array. Similarly, for set P_2, we have to compute the minimum and maximum value of y-coordinate among the last B points, which can be done using suffix minimum and suffix maximum array.
This way, we can after computing prefix/suffix arrays, try each dividing line one by one, compute f(P_1)+f(P_2) for each dividing line, and take minimum.
TIME COMPLEXITY
The time complexity is O(N*log(N)) due to sorting, rest is O(N), per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxs = 1e5, minv = 0, maxv = 1e9;
int n;
multiset<long long> s[2][2]; vector<pair<int, int>> v;
long long ans = LLONG_MAX;
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b){
return (a.second < b.second);
}
void Cal(int t){
for(int i = 0; i < n; i++){
long long val = 0;
for(int j = 0; j < 2; j++){
val += s[j][0].empty() ? 0 : (*(s[j][0].rbegin()) - *(s[j][0].begin())) * (*(s[j][1].rbegin()) - *(s[j][1].begin()));
}
ans = min(ans, val);
s[t][0].erase(s[t][0].find(v[i].first)); s[t][1].erase(s[t][1].find(v[i].second));
s[1 - t][0].insert(v[i].first); s[1 - t][1].insert(v[i].second);
}
}
int main()
{
int t; cin >> t;
while(t--){
cin >> n;
v.clear(); s[0][0].clear(); s[0][1].clear();
for(int i = 0; i < n; i++){
int x, y; cin >> x >> y;
s[0][0].insert(x); s[0][1].insert(y); v.push_back(make_pair(x, y));
}
ans = LLONG_MAX;
//vertical sweep 2nd rec starting from point of sweep
sort(v.begin(), v.end()); Cal(0);
//Horizontal sweep 2nd rec starting from point of sweep
sort(v.begin(), v.end(), sortbysec); Cal(1);
cout << ans << endl;
}
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <limits>
#ifdef HOME
#define NOMINMAX
#include <windows.h>
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T = readIntLn(1, 100'000);
int sumN = 0;
forn(tc, T)
{
int N = readIntLn(1, 100'000);
sumN += N;
vector<pair<int, int>> v(N);
for (auto& vi : v)
{
vi.first = readIntSp(0, 1'000'000'000);
vi.second = readIntLn(0, 1'000'000'000);
}
if (N == 1)
{
printf("0\n");
continue;
}
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
return a.first < b.first;
});
int64_t res = numeric_limits<int64_t>::max();
{
vector<int> miny(N, 1'000'000'000);
vector<int> maxy(N, 0);
vector<int> minyr(N, 1'000'000'000);
vector<int> maxyr(N, 0);
miny[0] = maxy[0] = v[0].second;
for (int i = 1; i < N; ++i)
{
miny[i] = min<int>(miny[i - 1], v[i].second);
maxy[i] = max<int>(maxy[i - 1], v[i].second);
}
minyr[N - 1] = maxyr[N - 1] = v[N - 1].second;
for (int i = N - 2; i > -1; --i)
{
minyr[i] = min<int>(minyr[i + 1], v[i].second);
maxyr[i] = max<int>(maxyr[i + 1], v[i].second);
}
for (int i = 1; i < N; ++i)
{
int64_t xa = v[0].first;
int64_t xb = v[i - 1].first;
int64_t ya = miny[i - 1];
int64_t yb = maxy[i - 1];
int64_t ar1 = (xb - xa) * (yb - ya);
int64_t xa2 = v[i].first;
int64_t xb2 = v[N - 1].first;
int64_t ya2 = minyr[i];
int64_t yb2 = maxyr[i];
int64_t ar2 = (xb2 - xa2) * (yb2 - ya2);
res = min(res, ar1 + ar2);
}
}
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
});
{
vector<int> minx(N, 1'000'000'000);
vector<int> maxx(N, 0);
vector<int> minxr(N, 1'000'000'000);
vector<int> maxxr(N, 0);
minx[0] = maxx[0] = v[0].first;
for (int i = 1; i < N; ++i)
{
minx[i] = min<int>(minx[i - 1], v[i].first);
maxx[i] = max<int>(maxx[i - 1], v[i].first);
}
minxr[N - 1] = maxxr[N - 1] = v[N - 1].first;
for (int i = N - 2; i > -1; --i)
{
minxr[i] = min<int>(minxr[i + 1], v[i].first);
maxxr[i] = max<int>(maxxr[i + 1], v[i].first);
}
for (int i = 1; i < N; ++i)
{
int64_t ya = v[0].second;
int64_t yb = v[i - 1].second;
int64_t xa = minx[i - 1];
int64_t xb = maxx[i - 1];
int64_t ar1 = (xb - xa) * (yb - ya);
int64_t ya2 = v[i].second;
int64_t yb2 = v[N - 1].second;
int64_t xa2 = minxr[i];
int64_t xb2 = maxxr[i];
int64_t ar2 = (xb2 - xa2) * (yb2 - ya2);
res = min(res, ar1 + ar2);
}
}
printf("%lld\n", res);
}
assert(sumN <= 100'000);
//assert(getchar() != -1);
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.util.function.BiFunction;
class DAREA{
//SOLUTIOn BEGIn
void pre() throws Exception{}
class pair{
int F, S;
pair(int a, int b){
F = a; S = b;
}
}
ArrayList<pair> al = new ArrayList<>();
void solve(int TC) throws Exception{
int n = ni();
al.clear();
for(int i = 0; i < n; i++)al.add(new pair(ni(), ni()));
int[] prefMin = new int[2+n], prefMax = new int[2+n], sufMin = new int[2+n], sufMax = new int[2+n];
prefMin[0] = Integer.MAX_VALUE;
sufMin[n+1] = Integer.MAX_VALUE;
Collections.sort(al, (A, B) -> A.F - B.F);
int p1, p2;
for(int i = 1; i<= n; i++){
p1 = al.get(i - 1).S; p2 = al.get(n - i).S;
prefMin[i] = Math.min(prefMin[i-1], p1);
prefMax[i] = Math.max(prefMax[i-1], p1);
sufMin[n - i + 1] = Math.min(sufMin[n - i + 2], p2);
sufMax[n - i + 1] = Math.max(sufMax[n - i + 2], p2);
}
long ans = (al.get(n - 1).F-al.get(0).F) * (long)(prefMax[n]-prefMin[n]);
int ps = al.get(0).F, pe = al.get(n - 1).F;
for(int i = 1; i< n; i++){
long a1 = (al.get(i - 1).F-ps) * (long)(prefMax[i]-prefMin[i]);
long a2 = (pe-al.get(i).F) * (long)(sufMax[i+1]-sufMin[i+1]);
ans = Math.min(ans, a1+a2);
}
Collections.sort(al, (A, B) -> A.S - B.S);
prefMin[0] = Integer.MAX_VALUE;
sufMin[1+n] = Integer.MAX_VALUE;
for(int i = 1; i<= n; i++){
p1 = al.get(i - 1).F; p2 = al.get(n - i).F;
prefMin[i] = Math.min(prefMin[i-1], p1);
prefMax[i] = Math.max(prefMax[i-1], p1);
sufMin[n - i + 1] = Math.min(sufMin[n - i + 2], p2);
sufMax[n - i + 1] = Math.max(sufMax[n - i + 2], p2);
}
ps = al.get(0).S; pe = al.get(n - 1).S;
for(int i = 1; i< n; i++){
long a1 = (al.get(i - 1).S-ps) * (long)(prefMax[i]-prefMin[i]);
long a2 = (pe-al.get(i).S) * (long)(sufMax[i+1]-sufMin[i+1]);
ans = Math.min(ans, a1+a2);
}
pn(ans);
}
//SOLUTIOn EnD
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new DAREA().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
