DAREA - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Prefix/Suffix Arrays.

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

6 Likes

Hi , can anyone please suggest where I am going wrong in this solution:

#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include <bits/stdc++.h>

using namespace std;

void printBox(long long box[])
{
    cout<<"[ ";
    for(long long i=0;i<4;i++)
        cout<<box[i]<<" ";
    cout<<"]\n";
}

bool inquad(long long quad[],pair<long long,long long> point)
{
    long long x = point.first;
    long long y = point.second;
    //printBox(quad);
    //cout<<x<<","<<y<<"\n"; 
    if(x>=quad[0] and y>=quad[2] and x<=quad[1] and y<=quad[3])
        {
            return true;
        }
    return false;
}

long long area(long long box[])
{
    return (box[1]-box[0])*(box[3]-box[2]);
}
long long join(long long box1[],long long box2[])
{
    long long f1=box1[0];
    long long f2=box2[0];
    if(f1 ==-1 and f2 == -1)
        return 0;
    if(f1 == -1)
        return area(box2);
    if(f2 == -1)
        return area(box1);

    long long b[4];
    b[0] = min(box1[0],box2[0]);
    b[1] = max(box1[1],box2[1]);
    b[2] = min(box1[2],box2[2]);
    b[3] = max(box1[3],box2[3]);
    return area(b);
}

void updateBox(long long (&box)[4],pair<long long,long long> point)
{
    long long x = point.first;
    long long y = point.second;

    if(box[0] == -1 or box[0]>x)
        box[0] = x;
    if(box[1] == -1 or box[1]<x)
        box[1] = x;
    if(box[2] == -1 or box[2]>y)
        box[2] = y;
    if(box[3] == -1 or box[3]<y)
        box[3] = y;
}


pair<long long,long long> points[100002];

int main()
{
    // ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
    long long T;
    cin>>T;
    while (T--)
    {
        long long N;
        cin>>N;
        //vector<pair<long long,long long>> points;
        long long left = -1, right = -1, top = -1, bottom = -1;
        for(long long i=0;i<N;i++)
        {
            long long x,y;
            cin>>x>>y;
            points[i] = make_pair(x,y);
            if(left == -1 || left>x)
            {
                left = x;
            }
            if(right == -1 || right<x)
            {
                right = x;
            }
            if(top == -1 || top>y)
            {
                top = y;
            }
            if(bottom == -1 || bottom<y)
            {
                bottom = y;
            }
        }
        long long midx = (left+right)/2;
        long long midy = (top+bottom)/2;

        long long Q[4][4];
        
        // cout<<left<<" "<<right<<" "<<top<<" "<<bottom<<"\n";
        Q[0][0] = left;
        Q[0][1] = midx;
        Q[0][2] = top;
        Q[0][3] = midy;
        
        Q[1][0] = midx;
        Q[1][1] = right;
        Q[1][2] = top;
        Q[1][3] = midy;
        
        Q[2][0] = left;
        Q[2][1] = midx;
        Q[2][2] = midy;
        Q[2][3] = bottom;

        Q[3][0] = midx;
        Q[3][1] = right;
        Q[3][2] = midy;
        Q[3][3] = bottom;

        long long box[4][4];
        for(long long i=0;i<4;i++)
            for(long long j=0;j<4;j++)
                box[i][j]=-1;
        for(long long i=0;i<N;i++)
        {
            for(long long j=0;j<4;j++)
            {
                if(inquad(Q[j],points[i]))
                {
                    updateBox(box[j],points[i]);
                    break;
                }
            }
        }

        long long a1 = join(box[0],box[1])+join(box[2],box[3]);
        long long a2 = join(box[0],box[2])+join(box[1],box[3]);

        cout<<min(a1,a2)<<"\n";
    }
}

how is multi set used here?

@taran_1407
You have written here that sides will not touch of two rectangle according to this if I am not wrong. But I do not think it is true.

Also, test cases were weak, my code passed AC but fails at:
1
19
1 1
2 1
3 1
1 2
1 3
1 4
1 5
3 2
3 3
3 4
3 5
3 6
3 7
3 8
4 8
5 8
5 7
5 6
5 5

@emotiological
what is the expected o/p for this tc ?

14

1 Like

I tried with my code and its giving me ans 14
but it is giving me wrong ans for all the subtasks , i dont know why ?

https://www.codechef.com/viewsolution/47844020

Here is link to my query

Can you plz tell me whats wrong with my code , It will be really helpful .

After sorting the points by X then Y, I used a binary tree for the minimum Y and another for the maximum Y. Then for any range of points from 1 to K we can find the minimum or maximum Y from the corresponding tree in O(log N) time. To evaluate possible horizontal divisions I swap the X and Y coordinates of all the points and use the same code as for vertical divisions. The overall rime complexity remains O(NlogN). You can see my solution at Solution: 47653161 | CodeChef

I am unable to understand the solution even after watching the editorial video 3 times. I’ve understood how the prefix and suffix arrays are being calculated and all the other stuff. But not understanding why did they do it. Any suggestions?! Pls help.

1 Like

I don’t think the test cases had a scenario where the sides of rectangles touch each other. Following is a test case for that scenario where Author’s solution fails! (while the Editor’s solution is correct). The correct ans is 55 while Author’s solution gives 56.

1
20
3 5
9 0
5 2
3 1
9 6
0 6
5 6
7 7
2 9
4 7
6 3
2 3
7 6
8 6
6 4
1 7
2 5
9 4
5 5
2 2

The two rectangles represented by lower-left corner and upper-right corner are {(0, 6), (2, 9} and {(2, 0), (9, 7)}

1 Like

I got 3 AC out of 4 but just can’t find why it fails on 4th case . Also I used ordered map . I only used only minimum y and maximum y [thats why map used ] for a particular x while sorting in x , and then i increased area for left rectangle and decreased for right rectangle while moving from left to right . If anyone can review code , I would be helpful

‘’’

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
ll int grid[n][2];
// vector<pair<int,int>> xy;
for(int i=0;i<n;i++)
{
cin>>grid[i][0]>>grid[i][1];
// xy.push_back({grid[i][0],grid[i][1]});
}

     //sort(xy.begin(),xy.end());
     
     map<ll int,ll int> largemap;
     map<ll int,ll int> smallmap;
     for(int i=0;i<n;i++)
     {
         largemap[grid[i][0]]=max(largemap[grid[i][0]],grid[i][1]);
     }
     
     for(int i=0;i<n;i++)
     {
         if(smallmap.find(grid[i][0])!=smallmap.end())
         {
             smallmap[grid[i][0]]=min(smallmap[grid[i][0]],grid[i][1]);
         }
         else
         smallmap[grid[i][0]]=grid[i][1];
     }
     
     
     
map<ll int,ll int>::reverse_iterator big=largemap.rbegin();
map<ll int,ll int>::reverse_iterator small=smallmap.rbegin();
ll int miny[smallmap.size()];
ll int maxy[largemap.size()];
maxy[largemap.size()-1]=big->second;
miny[smallmap.size()-1]=small->second;
big++;
small++;
 int index=largemap.size()-2;
//map<int,int>::iterator starting=largemap.begin();
//starting--;
//map<
for(;big!=largemap.rend();big++)
{
    maxy[index]=max(big->second,maxy[index+1]);
    miny[index]=min(small->second,miny[index+1]);
    small++;
    index--;
}
    //for(int i=0;i<largemap.size();i++)
//    cout<<maxy[i]<<" "<<miny[i];
  //  cout<<endl;

map<ll int,ll int>::iterator start=largemap.begin();
map<ll int,ll int>::iterator startmin=smallmap.begin();

map<ll int,ll int>::iterator constantmax=largemap.begin();
map<ll int,ll int>::iterator constantmin=smallmap.begin();

map<ll int,ll int>::iterator initial=smallmap.begin();

map<ll int,ll int>::reverse_iterator end=largemap.rbegin();
ll int leftmaxy=start->second;
ll int leftminy=startmin->second;
//cout<<leftmaxy<<leftminy;
//cout<<end->first<<start->first;
ll int totalarea=(maxy[0]-miny[0])*((end->first)-(start->first)); 
//ll int totalarea=LONG_MAX;
start++;
startmin++;
int ind=1;
for(;start!=largemap.end();start++)
{
    leftminy=min(leftminy,constantmin->second);
    leftmaxy=max(leftmaxy,constantmax->second);
    //cout<<leftminy<<leftmaxy;
    //cout<<(leftmaxy-leftminy)*((constantmax->first)-(initial->first));
  //  cout<<endl;
 totalarea=min(totalarea,(maxy[ind]-miny[ind])*((end->first)-(start->first)) + (leftmaxy-leftminy)*((constantmax->first)-(initial->first)));
    
    startmin++;
    constantmin++;
    constantmax++;
    ind++;
}
//cout<<totalarea<<endl;
ll int firstresult=totalarea;

//------------------------------------------------------------
//for y now , similar approach , its just copy paste of above code with grid changed from x,y to y,x
//------------------------------------------------------------

for(int i=0;i<n;i++)
{
ll int temp=grid[i][0];
grid[i][0]=grid[i][1];
grid[i][1]=temp;
}
largemap.clear();
smallmap.clear();
for(int i=0;i<n;i++)
{
largemap[grid[i][0]]=max(largemap[grid[i][0]],grid[i][1]);
}

     for(int i=0;i<n;i++)
     {
         if(smallmap.find(grid[i][0])!=smallmap.end())
         {
             smallmap[grid[i][0]]=min(smallmap[grid[i][0]],grid[i][1]);
         }
         else
         smallmap[grid[i][0]]=grid[i][1];
     }
     
     
     
 big=largemap.rbegin();
 small=smallmap.rbegin();
for(int i=0;i<largemap.size();i++)
{
    miny[i]=0;
    maxy[i]=0;
}
maxy[largemap.size()-1]=big->second;
miny[smallmap.size()-1]=small->second;
big++;
small++;
index=largemap.size()-2;
for(;big!=largemap.rend();big++)
{
    maxy[index]=max(big->second,maxy[index+1]);
    miny[index]=min(small->second,miny[index+1]);
    small++;
    index--;
}
    //for(int i=0;i<largemap.size();i++)
//    cout<<maxy[i]<<" "<<miny[i];
  //  cout<<endl;

     start=largemap.begin();
 startmin=smallmap.begin();

 constantmax=largemap.begin();
 constantmin=smallmap.begin();

 initial=smallmap.begin();

 end=largemap.rbegin();
leftmaxy=start->second;
leftminy=startmin->second;
//cout<<leftmaxy<<leftminy;
//cout<<end->first<<start->first;
 totalarea=(maxy[0]-miny[0])*((end->first)-(start->first)); 
//totalarea=LONG_MAX;
start++;
startmin++;
ind=1;
for(;start!=largemap.end();start++)
{
    leftminy=min(leftminy,constantmin->second);
    leftmaxy=max(leftmaxy,constantmax->second);
    //cout<<leftminy<<leftmaxy;
    //cout<<(leftmaxy-leftminy)*((constantmax->first)-(initial->first));
  //  cout<<endl;
 totalarea=min(totalarea,(maxy[ind]-miny[ind])*((end->first)-(start->first)) + (leftmaxy-leftminy)*((constantmax->first)-(initial->first)));
    startmin++;
    constantmin++;
    constantmax++;
    ind++;
}
ll int secondresult=totalarea;
cout<<min(firstresult,secondresult)<<endl;

}
}

‘’’

I thought I had a valid approach that would work but it didn’t. Now I’m struggling to find out why.

  1. Sort all points by their X coordinates
  2. Iterate over the list and find two points next to each other in the sorted list that have the greatest distance across the X axis. Let these points me A and B.
  3. Find the area of the rectangle containing all points from the beginning of the list to A, and then from B to end of the list. Add these two up.

Repeat the same for a list sorted across Y axis.

Return the minimum of the result obtained by the above two procedures.

When does this approach not work and why??

That is partially correct , As I spent good amt . of hours with this problem . Following your words, There can be a case where when you merge A point in left rectangle, there can be a huge difference in y-coordinates.Lets call ydiff=ymax-ymin seen till x=A.[so the area would be

(Ax-0)*ydiff

(difference in y coordinates seen till now which could be huge) ] assuming first point starts at x=0.

Now when You take B point in right rectangle , there could be low variation in ycoordinates . Hence area for right rectangle (xmax-Bx )*ydiff.

Here ydiff is difference between maxy and min y from x=b to x=xmax

Now although A and B could be x coordinates with large difference but if we take A in
right rectangle and due to low variance in y , we might consider it to merge in right rectangle so that area could be low as area also contains another component which is
ydiff
I hope explanation is clear

Anyone used same approach on python3 or any different approach, i am struggling to follow the same on python someone help!

hey i tried exact same approach:
result only one test case passed Solution: 47749126 | CodeChef
i figured what was wrong after :

consider the case:

seperating rectangles vertically
ans1 = left rectangle + right rectangle
= (4-2)x(3-1) + (4-2)x(5-5)
= 4
seperating rectangles horizontally
ans2 = upper rectangle+ bottom rectangle
=(4-3)x(5-3)+(5-1)x(2-2)
= 2

you can see ans2 < ans1
hope you understood the test case here :blush:

Hi, so I tried the brute force approach and wrote a code in python to test my idea… while it gives me correct output to every testcase I’m providing, when submitted I get WA

Can someone help me figure out what’s wrong?

This is my code:

def bb(c):

    min_x = 1e10
    min_y = 1e10
    max_x = -1
    max_y = -1

    for i in c:
        if i[0] < min_x: min_x = i[0]
        if i[0] > max_x: max_x = i[0]
        if i[1] < min_y: min_y = i[1]
        if i[1] > max_y: max_y = i[1]

    return [(min_x,min_y),(max_x,max_y)]

def bba(c, d):

    e = bb(c)
    f = bb(d)

    if(min(e[1][0], f[1][0]) <= max(e[0][0], f[0][0]) or min(e[1][1], f[1][1]) <= max(e[0][1], f[0][1])):
        ea = (e[1][0]-e[0][0])*(e[1][1]-e[0][1])
        fa = (f[1][0]-f[0][0])*(f[1][1]-f[0][1])
        return ea + fa
    return 1e10

t = int(input())
for i in range(t):
    n = int(input())
    p = [[0, 0]]*n
    q = 1e10
    for i in range(n):
          p[i] = [int(i) for i in input().split()]
    if n == 1: print(0)
    else:
        x = sorted(p, key= lambda a: a[0])
        y = sorted(p, key= lambda a: a[1])
        for i in range(n):
            q = min(bba(x[:i], x[i:]), q)
            q = min(bba(y[:i], y[i:]), q)
    print(int(q))

Thanks in advance!

https://www.codechef.com/viewsolution/47870455

can anyone please tell me where I am going wrong?

Solution satisfying this testcase.

Just check the same conditions and finding the minimum answers as the solution suggests.
But now you have to sort the coordinate array in 2 ways:

First array (coordinates stored as (x, y) in each pair):
First is the normal sort with (x1 < x2, or if x1 == x2 then y1 < y2)
Second sort is with (x1 > x2, or if x1 == x2 then y1 > y2)

Second array (coordinates stored as (y, x) in each pair):
First is the normal sort with (y1 < y2, or if y1 == y2 then x1 < x2)
Second sort is with (y1 > y2, or if y1 == y2 then x1 > x2)

You can also use one array and sort them in 4 ways using lambda sort and do the same process but taking 2 different array for (x, y) and (y, x) arrangement was easier to understand and implement.

By checking all the conditions on both the arrays we will cover all the possible rectangles that could be created and our solution will always be non - overlapping since overlapping case will have greater area than the non - overlapping counterpart.

I have been trying to solve this problem and my Code works correctly on all the test cases I can find even on some random test cases but it doesn’t always gives WA error when i try to submit. can Anyone help me with it.

Here is my code

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int n;

int sol(vector<pair <int, int>> cord) {

ll MIN, MAX = 0;

vector<pair<int, int>>cordR(n), prefix(n), suffix(n);

ll area = 0, sol = 1e9;

// X - Vertical line

for (int i = 0; i < n; i++)

{

    if (i == 0)

    {

        MIN = cord[i].second;

        MAX = cord[i].second;

    }

    else

    {

        MIN = min(cord[i].second, prefix[i - 1].first);

        MAX = max(cord[i].second, prefix[i - 1].second);

    }

    prefix[i] = {MIN, MAX};

}

for (int i = n - 1; i >= 0; i--)

{

    if (i == (n - 1))

    {

        MIN = cord[i].second;

        MAX = cord[i].second;

    }

    else

    {

        MIN = min(cord[i].second, suffix[i + 1].first);

        MAX = max(cord[i].second, suffix[i + 1].second);

    }

    suffix[i] = {MIN, MAX};

}

// Area for Vertical line

for (int i = 0; i < n; i++)

{

    if (n <= 2)

    {

        area = 0;

    }

    else if (i == 0 || i == (n - 1))

    {

        area = abs((cord[1].first - cord[n - 1].first) * (prefix[n - 1].second - prefix[n - 1].first));

    }

    else

    {

        area = abs((cord[i].first - cord[0].first) * (prefix[i].second - prefix[i].first) +

                   (cord[n - 1].first - cord[i + 1].first) * (suffix[i + 1].second - suffix[i + 1].first));

    }

    sol = min(sol, area);

}

return sol;

}

int main() {

int t;

cin >> t;

while (t--) {

    cin >> n;

    int sol1, sol2, x, y;

    

    vector <pair <int, int>> cord(n), cordR(n);

    

    for(int i = 0; i < n; i++) {

        cin >> x >> y;

        cord[i].first  = x;

        cord[i].second = y;

        cordR[i].first = y;

        cordR[i].second = x;

    }

    sort (cord.begin(), cord.end());

    sort (cordR.begin(), cordR.end());

    sol1 = sol(cord);

    sol2 = sol(cordR);

    

    cout << min(sol1, sol2) << "\n";

}

}

I have a similar type of approach but gives me correct output to every testcase I’m providing, when submitted I get WA. I don’t know what the problem is but if you find an please let me know