PROBLEM LINK:
Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Sort, Divide and Conquer
PROBLEM:
Given N points in a plane, find out three points A, B and C such that |AB| + |BC| + |CA is smallest.
EXPLANATION:
Classical 2 points (Closest Points)
This is a classical problem that finding out the closest 2 points. We can deal with that using divide and conquer.
Initially, we sort all the points P[1…N] by their X values, from small to large.
Now, suppose we are handling the answer in points between indices l and r, i.e. the closest points in P[l…r].. First of all, we divide them into 2 parts and recursively calculate the closest points problem. That is, find out the answer in P[l…m] and P[m+1…r]. Assume the minimum answer is A. Then, we try to update the answer using the points from different parts, i.e. |P[i] – P[j]|, where l <= i <= m < j <= r. Instead of bruteforce enumeration, we can use the current answer A to prune. It is easy to prove that there are only a small constant of points within the square [P[i].x, P[i].x + A] X [P[i].y, P[i].y + A] (Otherwise, the current minimum should be less than A). Therefore, we can further sort the points in P[l…r] in the order of Y coordinate, scan them one by one, and use the bruteforce enumeration inside the small square to update the answer.
If we use quick sort every time, the time complexity should be O(Nlog^2N). However, we can apply merge sort for the sorting of Y values, and thus the time complexity could be reduced to O(NlogN).
Original Question
Similar ideas could be applied to 3 points. The only difference is that the constant bound of the points in that small square may be different.
It is an accident that both setter and tester did not realize there existed a same problem in Google Codejam 2009 Finals. You can also check their editorials for more information.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.
