1. (30 pts.) The loneliest point Given a set of n points in the plane, let the loneliest point be the point which is furthest away from all other points. There could be multiple loneliest points if there are ties; e.g. in a set of two points both are loneliest. Suppose we tried to find a loneliest point using divide-and-conquer in the following way: 1: function FIND-LONELIEST(a list P of n points) 2: Sort P in order of increasing x coordinate (say breaking ties with the y coordinate) 3: p,dp + HELPER(P) 4: return p 5: function HELPER(P[0..n-1]) 6: # Return a loneliest point in P and its distance to the nearest point. if n=1 then return (P[0],-) m+ [n/2] left-points + P(0..m 1] 10: right points + P[m..n-1] 11: l,der HELPER(left points) # Recursively find loneliest points in left and right halves r,dp + HELPER(right points) det min(de, min peright-points d(l,p)) # Check distance from l to all points on right dr + min(d,, min pEleft-points d(r, p)) # Check distance from r to all points on left 15: if de