You are not logged in. Please login at to post your questions!


ACM14KP1 - Editorial



Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang




Sort, Divide and Conquer


Given N points in a plane, find out three points A, B and C such that |AB| + |BC| + |CA is smallest.


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.


Solutions will be available soon.

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 01 Dec '14, 09:24

shangjingbo's gravatar image

3★shangjingbo ♦♦
accept rate: 0%

edited 01 Dec '14, 12:24

admin's gravatar image

0★admin ♦♦

please correct me.. what I did was for the problem was that I compute a side and then i keep track of the minimum three sides thus obtained, i am getting a wrong answer for the problem. thanx in advance :)


answered 28 Oct '15, 00:46

smitthakkar's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 01 Dec '14, 09:24

question was seen: 3,094 times

last updated: 28 Oct '15, 00:46