2001년 가을학기 문제해결기법 중간고사

징검다리 건너기

친구들과 놀이 동산에 간 준성이는 징검다리 게임을 발견하게 된다. 이 게임에는 평행한 둑 사이에 물이 흐르는 개울이 있고, 개울을 건널 수 있는 징검다리용 돌이 놓여 있다. 징검다리용 돌은 모두 원형으로 반지름이 1[eqn: m]이며 서로 겹쳐지지 않는다. 개인의 점프 능력에 맞게 돌을 선택하여 개울을 건너게 되고, 점프 횟수가 작을수록 좋은 상품이 주어진다. 물론 개울물에 빠지면 상품을 받을 수 없다.

노트북 컴퓨터를 사용할 수 있음을 알고 이 상황을 아래 그림과 같이 양쪽 둑과 돌의 위치를 [eqn: x,y]-평면에 나타내었다. 그림에서 개울의 폭이 11[eqn: m]이므로 [eqn: y=0]인 직선과 [eqn: y=11]인 직선이 둑을 나타낸다. 번호가 붙은 디스크는 징검다리용 돌을 말한다.

한번에 1[eqn: m]를 점프할 수 있는 친구는 아래쪽 둑에서 8번, 9번, 3번, 그리고 6번 돌을 거쳐서 개울을 건널 수 있다. 2[eqn: m]를 점프할 수 있는 친구는 같은 방식으로 개울을 건널 수 있지만, 차례로 5, 7, 1번 돌을 지나서 개울을 건너면 점프 횟수를 줄일 수 있다.

여러분의 일은 준성이를 도와주는 프로그램을 작성하는 것이다. 개울의 폭과 징검다리용 돌의 위치가 입력으로 주어진다. 돌은 모두 원형이고 반지름이 1[eqn: m]이다. 그리고 개별 친구가 몇 [eqn: m]를 점프할 수 있는지 점프 능력이 주어질 때, 개울을 건너기 위해서 필요한 최소 점프의 수를 구해주어야 한다.

프로그램명은 jump.cpp(jump.c)라고 하고 실행 파일명은 jump.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 개울의 폭이 주어진다. 둘째 줄에는 징검다리용 돌의 수 [eqn: n]([eqn: n le 200])이 주어진다. 셋째 줄부터 [eqn: n]개의 줄에 각 돌의 [eqn: x,y]-좌표가 차례로 주어진다. 둘 사이에는 공백이 있다. 여기서 [eqn: 0 le x, y le 10000]이다. 그리고 친구의 수 [eqn: k]([eqn: k le 20])가 주어진다. 다음으로 친구들의 점프 능력이 몇 [eqn: m]인지가 주어진다. 징검다리용 돌의 수와 친구 수를 제외하고 입력되는 숫자는 모두 실수이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 입력된 순서로 친구들이  몇 회의 점프를 통하여 개울을 건널 수 있는지 그 최소 횟수를 출력한다. 개울을 건널 수 없는 경우는 -1을 출력한다.

입력과 출력의 예

INPUT.TXT

11.0

9

2.0 9.0

6.0 7.0

9.0 7.0

12.0 4.0

4.0 2.0

11.0 9.0

2.0 5.0

9.0 2.0

9.0 4.5

4

1.0

2.0

5.0

0.8

OUTPUT.TXT

5

4

2

-1