15109번 - Distinct Distances 다국어

You’re setting up a scavenger hunt that takes place in the two-dimensional plane.

You’ve already decided on n distinct points of interest labeled p₁, . . . , p_n. The point p_i is located at integer coordinates (x_i, y_i).

You now want to choose a point q for the final location. This point must have finite coordinates, but it does not necessarily need to have integer coordinates. This point also can coincide with one of the original points p_i.

In order to make this final location interesting, you would like to minimize the number of unique distances from q to the other points.

More precisely, you would like to choose q that minimizes |S(q)|, where S(q) is defined as the set

{|q − p₁|, |q − p₂|, . . . , |q − p_n|}.

Here, the notation |S(q)| means the number of elements in the set S(q) and |q − p_i| denotes the Euclidean distance between q and p_i. Note that S(q) is a set, so if two or more distances |q − p_i| are equal, they are counted as a single element in S(q).

Given the coordinates of the points, find the minimum value of |S(q)|.

Warning: Use of inexact arithmetic may make it difficult to identify distances that are exactly equal.

The first line of input contains a single integer n (1 ≤ n ≤ 40).

Each of the next n lines contains two space-separated integers x_i and y_i (|x_i|, |y_i| ≤ 300), representing the coordinates of p_i.

Output, on a single line, the minimum number of unique distances from q to all other points p_i.

For the first sample, we can let our point q be (0, 0). All other points are distance 5 away. For the second sample, we can let q be (1.5, 1.5).