시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 75 | 3 | 3 | 60.000% |
한 도시에 N개의 무선 통신 기지국이 있다. 각각의 기지국의 위치는 x, y 좌표로 표현되며 각 기지국의 좌표는 서로 다르다.
기지국에서는 특정 주파수의 전파를 이용하여 통신을 한다. 만약 두 기지국의 거리가 20을 넘지 않으면 두 기지국은 인접해 있다고 한다. 인접해 있는 두 기지국은 전파의 방해를 막기 위해 서로 다른 주파수를 사용해야 한다. 또한 주파수가 비슷할 경우 통신 장애가 발생할 수 있기 때문에, 2 이상 차이나야 한다고 하자. 편의상 주파수는 자연수만 고려하자.
무선 통신 기기를 만들 때에는 가능한 모든 주파수를 다 처리해 주어야 하기 때문에, 사용되는 주파수의 종류수가 적은 편이 유리하다.
무선 통신 기지국의 위치가 주어졌을 때, 사용되는 주파수의 최소 종류수를 구하는 프로그램을 작성하시오.
첫째 줄에 N(1 ≤ N ≤ 12)이 주어진다. 다음 N개의 줄에는 각 기지국의 좌표가 실수로 주어진다. 입력으로 주어지는 기지국의 위치는 비교적 넓게 퍼져 있어서, 각 기지국과 인접한 다른 기지국은 최대 4개이다.
기지국의 좌표는 절댓값이 200보다 작거나 같으며, 소숫점 둘째자리까지 주어진다.
첫째 줄에 주파수의 최소 종류수를 출력한다.
5 0 0 5 7.5 1 -3 10.75 -20.1 12.01 -22
3
6 0 1 19 0 38 1 38 21 19 22 0 21
2
ICPC > Regionals > North America > East Central North America Regional > 2003 East Central Regional Contest D번