시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 4 3 3 75.000%

문제

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 p1, . . . , pn. The point pi is located at integer coordinates (xi, yi).

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 pi.

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 − p1|, |q − p2|, . . . , |q − pn|}.

Here, the notation |S(q)| means the number of elements in the set S(q) and |q − pi| denotes the Euclidean distance between q and pi. Note that S(q) is a set, so if two or more distances |q − pi| 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 xi and yi (|xi|, |yi| ≤ 300), representing the coordinates of pi.

출력

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

예제 입력 1

8
3 4
0 5
0 -5
5 0
-5 0
4 -3
3 -4
-4 3

예제 출력 1

1

예제 입력 2

4
0 0
1 1
2 2
3 3

예제 출력 2

2

예제 입력 3

6
0 -5
1 0
-1 0
2 3
3 2
-3 0

예제 출력 3

3

힌트

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).