A Magical Length
Given n points A[1..n] in the 2-D plane, where i-th point has two attributes A[i].x and A[i].y representing x-coordinate and y-coordinate. Find 3 points A[i], A[j], A[k] (i, j, k are distinct) such that distance(A[i], A[j]) + distance(A[j], A[k]) + distance(A[k], A[i]) is minimized. Here distance(A[i], A[j]) means the Euclid Distance, which is equals to sqrt( (A[i].x - A[j].x)^2 + (A[i].y - A[j].y)^2) You need to output the minimum possible distance.
The first line contains an integer T indicating the number of test cases.
Each test case starts with a positive integer n indicating the number of points.
The following n lines contain two real numbers A[i].x and A[i].y with at-most 6 digits after decimal point describing the coordinates of the point.
Output T lines in total. Each line starts with "Case #: " and followed by minimum length. Here "#" is the number of the test case starting from 1.
Answers within an absolute or relative error of 10^-6 will be accepted
- 1 ≤ T ≤ 10
- 3 ≤ n ≤ 100000
- 0 ≤ A[i].x, A[i].y ≤ 10000
- A[i].x, A[i].y are real numbers with atmost 6 digits after decimal position.
Input: 1 4 0.0 0.0 2.0 2.0 2.0 0.0 1.0 1.0 Output: Case 1: 4.8284271247
One possible solution is to select these 3 points (0, 0), (2, 0), (1, 1), the length is sqrt(2) + sqrt(2) + 2
|Tags||acmkgp14, admin, divide-and-conq, easy-medium|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions