Find the distance between the most distant points in c++… how to solve this problem…
1 Like
The problem can be solved using the concept of Convex Hull. Once you get the convex hull of all the points the answer lies among the points on the boundary of the hull. Then the most distant points from the hull can be calculated in O(N) time (i.e. by looking at diagonally opposite points and checking distance with its neighbors).
One Implementation in C++ can be found here :
http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/
3 Likes
Perfect explanation
1 Like