## Closest pair of points

 Hide textShow text Hide pseudo-codeShow pseudo-code From the given set of points, find the pair closest to one other. Use the mergesort-based method described in the given pseudocode. ```1. Let min be a global floating point variable initialized to positive infinity 2. Let cp1 and cp2 be global point variables used to store the closest pair found so far 3. Let a be the array used to store the points, where the points are arranged in increasing order by their X coordinate 4. CLOSEST_PAIR(a,0,a.length-1) ``` ```CLOSEST_PAIR(Array a, int p, int r) 1. if p < r 2. q = (p+r)/2 3. middle = a[q].x 4. CLOSEST_PAIR(a,p,q) 5. CLOSEST_PAIR(a,q+1,r) 6. MERGE(a,p,q,r) 7. for each point between indices p and r 8. Let curr be the point being examined 9. if abs(curr.x - middle) < min 10. For the four previous examined points p1, ..., p4 11. Let p_i be a previous examined point 12. CHECK(curr,pi) ``` ```CHECK(Point p, Point o) 1. if o is null, return; 2. dist = sqrt((p.x-o.x)^2 + (p.y-o.y)^2) 3. if dist < min 4. min = dist 5. cp1 = o 6. cp2 = p ```