시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1665 | 848 | 629 | 49.333% |
당신은 세계적인 인간대포 서커스 공연자이다. 즉, 당신은 거대한 가짜 대포 안으로 기어올라가 먼 거리를 발사되며 사람들에게 기쁨을 주는 사람인 것이다. 오늘, 당신은 혼자가 아니다. 당신은 국제 인간대포 회의 겸 전시장에 와 있으며 이 곳에서는 수백명의 인간대포 전문가들이 서로의 경험을 공유하고 기술을 연마한다. 보통 당신의 서커스에서 당신은 한 대포만을 가지고 공연하는데 반해 이곳에서는 사용할 수 있는 수많은 대포가 있다.
여러 대포를 사용하면 회의장을 좀 더 편리하게 돌아다닐 수 있다. 만약 당신이 a장소에서 b장소까지 이동하려 한다면 a 부터 b까지 직선으로 걸어갈 수도 있고, 주변의 대포에 탑승해서 어딘가 다른 곳으로 발사되어 이동할 수도 있다. 발사되고 나면 내린 위치에서 도착점을 향해서 걸어갈 수도 있고, 다시 한 번 또 다른 대포를 이용하여 목적지에 더 빠르게 도착할 수도 있다. 그림 E.1처럼 배치된 지도에서 당신은 a에서 b로 이동하기 위하여 그림 E.2와 같은 경로로 걷거나 대포를 이용하여 움직일 수 있다. 화살표는 당신이 대포에서 발사되어 떨어진 점을 의미하며 직선은 당신이 달린 경로를 나타낸다.
그림 E.1
그림 E.2
당신은 5m/s의 속도로 달린다. 모든 대포는 당신을 당신이 원하는 임의의 방향으로 50m 날려줄 수 있다. 대포에 올라타고 발사되고 착륙하기까지는 정확히 2초가 걸린다. 대포는 장애물이 아니기 때문에 당신이 뛰는 도중에 대포가 있다면 점프해서 넘어가 마치 직선과 같이 움직일 수 있다. 당신의 현재 위치와 목적지의 위치, 그리고 대포들의 위치가 주어질 때 당신은 목적지에 가장 빨리가기 위한 경로를 알고 싶다.
입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대포의 숫자 정수 n이 주어진다. 남은 n줄에는 한 줄에 대포 하나의 위치 정보가 주어지며, 이는 실수로 주어지는 X, Y 좌표이다. 모든 좌표는 미터로 측정되었으며 n의 값은 0 이상 100 이하이다. 입력으로 주어지는 모든 X, Y좌표는 0 이상 500 이하의 실수이고, 소수점 아래로 최대 두 자리까지만 주어진다.
한 줄에 걸쳐 목적지에 다다르기 위해 가장 빠른 시간을 출력하라. 실제 답과 0.001초 미만의 차이는 정답으로 인정한다.
25.0 100.0 190.0 57.5 4 125.0 67.5 75.0 125.0 45.0 72.5 185.0 102.5
19.984901
ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2014 E번