시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 517 174 138 33.173%

문제

소수 마을들의 주민들은 매우 특이한 규칙을 준수한다. 규칙은 바로 “가고 싶은 위치까지의 거리가 소수일 경우에만 간다”라는 것이다. 소수 마을의 주민 승욱이는 소수 마을에서 멀리 떨어진 A마을에 볼일이 있어 그곳까지 가야한다. 소수 마을에서 A마을까지의 단숨에 가고 싶지만 안타깝게도 두 마을의 거리는 소수가 아닐 경우에는 그럴 수가 없다. 그럴 경우에는 다른 마을들을 경유하여 가야한다. (경유하는 마을도 현재 위치에서의 거리가 소수일 경우에만 갈 수 있다.) 소수 마을과 경유할 수 있는 마을들, 그리고 A마을의 위치가 좌표평면 상으로 주어질 때, 승욱이가 소수 마을의 규칙을 준수하여 A마을로 갈 수 있는 최단의 길을 찾는 것을 도와주자. 소수 판정을 위해 마을 간의 거리는 정수 부분만으로 취급한다. 예를 들어, 거리가 3.1415라면 이를 버림하여 3만 취급한다.

입력

첫 번째 줄에 소수 마을의 위치 (X1,Y1) 와 A마을의 위치 (X2,Y2) 가 입력된다. 두 번째 줄에 경유할 수 있는 마을의 개수 N ( 0 ≤ N ≤ 4000 )가 입력된다. 세 번째 줄부터 N+2번째 줄까지 경유 할 수 있는 마을들의 위치 (X3,Y3)가 입력된다. 단, 각 마을들의 좌표는 절댓값이 3000을 넘지 않는 정수이다.

출력

소수 마을의 규칙을 준수하여 A마을까지 가는 방법 중 제일 짧은 거리로 갈 수 있는 길의 거리합을 출력한다. 만약 소수 마을의 규칙을 준수하여 갈 수 있는 방법이 없는 경우 -1을 출력한다.

예제 입력 1

1 2 5 4
2
4 1
6 2

예제 출력 1

6

예제 입력 2

1 2 5 4
0

예제 출력 2

-1

힌트

출처

High School > 선린인터넷고등학교 > 머그컵 D번