시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 12 3 3 100.000%

문제

한 도시에 N개의 무선 통신 기지국이 있다. 각각의 기지국의 위치는 x, y 좌표로 표현되며 각 기지국의 좌표는 서로 다르다.
  기지국에서는 특정 주파수의 전파를 이용하여 통신을 한다. 만약 두 기지국의 거리가 20을 넘지 않으면 두 기지국은 인접해 있다고 한다. 인접해 있는 두 기지국은 전파의 방해를 막기 위해 서로 다른 주파수를 사용해야 한다. 또한 주파수가 비슷할 경우 통신 장애가 발생할 수 있기 때문에, 2 이상 차이나야 한다고 하자. 편의상 주파수는 자연수만 고려하자.
  무선 통신 기기를 만들 때에는 가능한 모든 주파수를 다 처리해 주어야 하기 때문에, 사용되는 주파수의 종류수가 적은 편이 유리하다.
  무선 통신 기지국의 위치가 주어졌을 때, 사용되는 주파수의 최소 종류수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤12)이 주어진다. 다음 N개의 줄에는 각 기지국의 좌표가 실수로 주어진다. 입력으로 주어지는 기지국의 위치는 비교적 넓게 퍼져 있어서, 한 기지국에는 최대 4개(물론 자기 자신을 제외하고)의 기지국만 인접해 있다고 가정하자.

출력

첫째 줄에 주파수의 최소 종류수를 출력한다.

예제 입력

5
0 0
5 7.5
1 -3
10.75 -20.1
12.01 -22

예제 출력

3

힌트