CLOSEST - Closest Triplet
Closest pair is an old problem that asks to find, given a set of N points in the plane,
the pair that minimizes the distance between them. This problem can easily be solved
using roughly N 2 operations by testing all possible pairs of points and keeping at each
step the optimal pair. With a more clever approach, the problem has been solved using
∼ N log N operations.
Closest triplet is an analogous problem which also takes a set of N points as input, and
asks for the triplet (group of three points) that minimizes the sum of the three distances
between each pair of them. In this case there is also a trivial solution that tests all possible
triplets using roughly N3 operations. However, since you are a clever programmer, we
are confident that you are able to find a better algorithm.
The input contains several test cases, each one described in several lines. The first line
contains an integer N indicating the number of points in the set (3 ≤ N ≤ 3000). Each
of the next N lines describes a different point of the set using two integers X and Y
separated by a single space (1 ≤ X, Y ≤ 106 ); these values represent the coordinates of
the point in the XY plane. You may assume that within each test case no two points
have the same location. The last line of the input contains a single −1 and should not
be processed as a test case.
For each test case output a single line with a real number representing the sum of the
distances between each pair of points of any closest triplet of the set of points. Round
the result to the closest rational number with three decimal places. In case of ties, round
up. Always use exactly three digits after the decimal point, even if it means finishing
with a zero.
I wanted to mention, that I didn't like the joke about closest rational number.
Any submission to this problem causes a disaster.
@Pablo, can you please give me a test case my program fails on? I wrote a script to test the N^3 brute force with mine, and I got all of them correct... This is frustrating
Pablo Ariel Heiber:
the faster way was not the intended way in the competition (not necessarilly, at least)
this is 4 minute problem and this problem make the judge to wait for more time