Ohhhh …I forgot that , for convex hull , in main function try printing finalreq vector …anyways thank you for responding 
@harry_shitt , Found this test case where your code fails
1
7
1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Hi can anybody plz tell me or give a testcase where my code is failing I did it without using convex hull with the help of slopes
Here is my code CodeChef: Practical coding for everyone
I am not able to understand the convex hull part explained by the editorialist in the vedio. can any one exlpain that part in a bit detail , i am trying to understand the code explanation since yesterday but couldn’t able to grasp the topic , please help !!
Thank you so much for that! I thought of the exact same approach, but I wasn’t able to implement it correctly in my case. 
Those commenting here that they used stacks , infact it is convex hull azpproach using stacks.
i doubt all those solutions which used stacks are copied thats why they dont know the real logic and motivation behind the problem
As majority of solutions to this problem are copied
@yosay55777 , i also solved the problem using stacks , but i don’t know covex hull implementation , we don’t need convex hull here , that was more generic algorithm which find’s the convex hull for given set of any points . But in this problem the points are spaced equally and one after another , we can make the observation that if the slope of the line segment of i and i-1 is less than the slope of previous longest line segment from i-1 we can join the line segments and make new valid line segment.
how can you say this vague statement blaming everyone who used stack in their implementation ??
Can you share intuition behind your code?
Let me try to share the intuition behind it, although it might be not perfect.
Aim:- we have to find maximum distance two points which are visible from each other.(points means peak points of mountain)
observation:-
->If we are at point i then we can see any point j (i<j<=n) ,if there is no hindrance between them or in simple words there is no points between i to j which crosses(it is allowed to touch but not to cross it) the line segment between point i and j. this is possible when slope of i and j is greater than slope of i and every l in range (i<l<j).
Intuition or solution(brute force) based on this observation will be:-
lets find farthest visible point k for every i and find the max answer ( max(k-i) for every i)
complexity:- O(N^2)
observation:-
->let’s say we have find k for some i, now for every j (i<j<k) k’ {k’ is k for j} will be <= k
{L(a,b):- line segment between point a and b}
proof:-
let’s say that k’ for some j be >k this implies that j can see beyond k, thus L(j,k’) intersects L(i,k)
case 1:- it intersects after k or at k
this mean that our k for i is wrong it should be <=j
case 2:- it intersects before k
this mean that our k for i is wrong it should be >=k’
we can now say that k’ for every j (i<j<k) will be between i and k so it will always be lesser than k-i
Intuition or optimized solution based on this observation will be:-
lets find farthest farthest point k for i and directly jump i to k or not to iterate for that points between i and k.
{now onwards in below statements may be I am wrong}
complexity:- it is not O(N^2)
observation:-
->also one thing to notice is that slope of L(i,k) > slope of L(k,k’) {where k’ is new farthest point for i=k}
it will make sure that jumps will be more bigger or frequency of future jumps will be less.
4 Likes
Can anyone help me out with this code??
#include<bits/stdc++.h>
using namespace std;
#define loop(i,n) for(int i=0;i<n;i++)
#define ll long long
#define scan(arr) for(auto &it:arr)cin>>it;
#define print(a) {for(auto it:a)cout<<it<<" ";cout<<endl;}
float slope(int x1,int y1,int x2,int y2)
{
return float(y2-y1)/float(x2-x1);
}
int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int h[n];
scan(h);
int ans[n];
float curr_slope=INT_MIN,bestslope=INT_MIN;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(slope(i,h[i],j,h[j])>=curr_slope)
{
curr_slope=slope(i,h[i],j,h[j]);
bestslope=max(curr_slope,bestslope);
ans[i]=j-i;
}
}
curr_slope=INT_MIN;
bestslope=INT_MIN;
}
int maxi=INT_MIN;
for(int i=0;i<n-1;i++)
{
maxi=max(maxi,ans[i]);
}
cout<<maxi<<endl;
}
return 0;
}
I think the test cases in this question were weak, as I was getting TLE for last task, of last sub task, and then I made loop to break after, 10^8 iterations, and instead of WA i got AC.
Thankyou man!
Did anyone solve it using Jarvis March if yes please share code
In the Setter’s solution,
Shouldn’t it be ans = max(ans, i - ch.back().x);?
( instead of ch.back().y )
no , setter is taking height as x and distance as y. check the solution again. x is ar[i] and y is i.
Oh thanks a lot buddy 
I’ve been using the scipy.spatial.ConvexHull to solve this problem and I think it works, but I’m getting AC for most of the cases but WA for two and I’m not sure why. I’ve converted everything to a float and tried many different for finding the distances. Does anyone have any suggestions or things that I could try? CodeChef: Practical coding for everyone