×

# ACM14KP1 - Editorial

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

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.

This question is marked "community wiki".

161446376
accept rate: 0%

19.8k350498541

 0 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. https://ideone.com/1x1AfI thanx in advance :) answered 28 Oct '15, 00:46 11 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×1,722
×138
×40
×2

question asked: 01 Dec '14, 09:24

question was seen: 3,668 times

last updated: 28 Oct '15, 00:46