#include <bits/stdc++.h>
using ll=long long;
using namespace std;
typedef struct point
{
ll x;
ll y;
};
bool sortPoint(point a,point b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int main()
{
int n;
cin>>n;
point arr[n];
for(int i=0; i<n; i++)
{
cin>>arr[i].x;
cin>>arr[i].y;
}
int mn[n];
ll mxArea=0;
sort(arr,arr+n,sortPoint);
for(int i=n-1; i>=0; i--)
{
if(i==n-1)
mn[i]=500;
else
mn[i]=min((int)arr[i+1].y,mn[i+1]);
}
ll minAll=min((int)mn[0],(int)arr[0].y);
mxArea=arr[0].x*500;
mxArea=max((int)mxArea,(int)minAll*100000);
for(int i=0; i<n-1; i++)
{
ll tmp1=(arr[i+1].x-arr[i].x)*500;
ll tmp2=(100000-arr[i].x)*mn[i];
mxArea=max((int)mxArea,max((int)tmp1,(int)tmp2));
}
mxArea=max((int)mxArea,(int)(100000-arr[n-1].x)*500);
stack<ll> stack;
stack.push(0);
stack.push(arr[0].y);
for(int i=0; i<n-1; i++)
{
while(arr[i+1].y<stack.top())
{
ll tmp1=stack.top();
stack.pop();
ll tmp2=stack.top();
stack.pop();
ll area=tmp1*(arr[i+1].x-tmp2);
mxArea=max((int)mxArea,(int)area);
if(stack.empty())
break;
}
stack.push(arr[i].x);
stack.push(arr[i+1].y);
}
while(!stack.empty())
{
ll tmp1=stack.top();
stack.pop();
ll tmp2=stack.top();
stack.pop();
ll area=tmp1*(100000-tmp2);
mxArea=max((int)mxArea,(int)area);
}
cout<<mxArea<<endl;
}
I have tried to debug this for 2 days. Please help me to understand why I failed on the second test case. Just give any test case that my code produce wrong ans. Thanks