Can anyone please explain their approach and share their code for the problem Rectangle from ZCO at CodeChef: Practical coding for everyone ?
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();
}
Thank you
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.
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)
I got it, thank you so much.