I use map to store x and y coordinates so x coordinates are already sorted.
I can think of only two triangle types one with h=500 and l=(x2-x1) , x2 nd x1 are adjacent .
Other being, l=10^5 - x1 and h=the least height AFTER this coordinate. Are their any other possibilies?
Hrs my code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll min(ll a,ll b)
{
return a>b?b:a;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
int main() {
ll n;
cin>>n;
map<ll,ll>mp;
for(ll i=0;i<n;i++)
{
ll x,y; cin>>x>>y; mp[x]=y;
}
if(mp.find(0)==mp.end())
mp[0]=0;
if(mp.find(pow(10,5))==mp.end())
mp[pow(10,5)]=500;
ll m=mp.size();
ll suff[m],index=m-1,temp=500;
for(auto i=mp.rbegin();i!=mp.rend();i++)
{
if(i==mp.rbegin())
{suff[index–]=i->second;temp=i->second;}
else
suff[index–]=temp;
temp=min(i->second,temp);
}
index=0;temp=0;
for(auto i=mp.begin();i!=mp.end();i++)
{
ll diff=0;
auto j=i;j++;
if(j!=mp.end())
diff=j->first-i->first;
temp=max(temp,max(diff500,suff[index++](pow(10,5)-i->first)));
}
cout<<temp;
return 0;
}