Question 1 (Closest Pair of Points, 35 points). [See also problem 2.32 in the tertbookj Consider the following algorithmic problem: Given n points (,yi) in the plane, find the pair of them whose Euclidean distance ((ri -x,)2 + (i y2) is as small as possible. There is an obvious O(n2) algorithm for this, but with a little effort, you can get it down to near linear time. Problem:Give a full near-linear time algorithm for closest pair of points Extended hint: An outline of a working algorithmwill look something like this CPP (S) If ISI