Help in Rectangle Problem from ZCO

Can anyone please explain their approach and share their code for the problem Rectangle from ZCO at CodeChef: Practical coding for everyone ?

@everule1 Please help.

First find the largest height possible at each position of x, by taking min(y) for all points with this x co-ordinate.
Then iterate over all possible heights of the rectangle, and find 2 points, such that their max height is less than y. Find the area of the rectangle between the 2 points with height y. Take the maximum of all such areas.

Code
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
const int MAX_X=1e5;
const int MAX_Y=500;
void solve(){
    int n;
    cin>>n;
    vector<int> maxh(MAX_X+1, MAX_Y);//Default maxheight is 500
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        maxh[a]=min(maxh[a], b);
    }
    maxh[MAX_X]=0;//Since we can't really go ahead
    int ans=0;
    for(int y=1;y<=MAX_Y;y++){
        int last=0;//That's the earliest we can start from
        for(int x=1;x<=MAX_X;x++){
            if(maxh[x]<y){//If we can't go through this point
                int currans=x-last;//X distance
                currans*=y;//Y distance
                ans=max(ans,currans);//Take the maximum area
                last=x;//This is now the lastpoint with maxh<y
            }
        }
    }
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
1 Like

Thank you :smiley:

I have a very silly doubt, like if we want to find the maximum area within the rectangle which lies on X axis, then why aren’t we taking maximum of all co-ordinates and calculating the area as (100000-MAX(x coordinate) ) * 500) ?

@everule1 Can you please share how you go about solving such problems, or in general any competitive programming problem? And how do you ascertain that the algorithm is indeed correct? And yes, your explanations are great! They have helped me many a times.

It’s not the same constants, but I think you’ll understand.

Actually in this picture, the maximum X coordinate is 9, hence shouldn’t the maximum area be:
(100000-9)*500 ?

As in the question, the bottom right corner is at (100000,0) and top left corner is at (0,500)

@pranshugupta

It’s not the same constants for the previous one

1 Like

I got it, thank you so much. :slight_smile: