시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 40 | 12 | 4 | 57.143% |
통계상으로 상업 비행기는 꽤 안전하다. 초창기의 비행기는 기술적인 측면에서 현재의 비행기에 비해 엔진 신뢰성이 낮아서 항로상에서 인근 공항으로 부터 60분 이상 떨어져서 비행하는 것을 금지했기 때문이다. 지금도 다양한 규칙들이 존재하지만 핵심 내용은 이 "60분의 규칙"과 비슷하다. 비행기가 가장 가까운 공항에서 허용된 최대 거리 이상 멀어지면 안 된다는 것이다. 이러한 제약 사항 때문에 비행기가 곧바로 공항까지 갈 수 없는 경우도 종종 있다.
우리는 최대 허용 거리를 준수하면서 주어진 두 공항 사이를 이동하는 최단 경로를 계산해야 한다. 아래 보이는 그림은 첫 번째 테스트 케이스에 대한 자료를 나타낸다. 비행기의 항로는 반드시 주어진 세개의 원 어딘가에 존재해야 하며 2번에서 3번 공항으로 이동하려면 반드시 1번 공항의 원을 거쳐야 한다. 비행기가 공항 1에 도착할 필요는 없다.
비행기의 연료는 제한되어있기 때문에 최단 경로보다 긴 경로로 이동할 경우 연료 부족으로 도중에 착륙해야 할 수도 있다. 따라서 연료 용량에 따라 공항 1까지 가야 하는 경우가 생길 수도 있다. 공항 1까지 가는데 필요한 연료도 부족한 경우엔 도착지 까지 갈 수 없는 경우이다.
위와 같은 가정을 아래처럼 단순화 할 수 있다.
각 테스트 케이스의 첫 번째 줄에 정수 N 과 R 이 주어진다 (2 ≤ N ≤ 25, 1 ≤ R ≤ 10 000). N은 공항의 수 이고 R은 최대 허용 거리(km)이다. 다음 N개의 줄에는 공항의 경도와 위도를 나타내는 정수 Φ, θ가 주어진다(0 ≤ Φ < 360, -90 ≤ θ ≤ 90). 공항의 번호는 각각 1부터 입력받은 순서로주어지며 두 공항이 같은 위치에 있는 경우는 없다.
이어지는 줄에는 정수 Q가 주어진다 (1 ≤ Q ≤ 100). 각각의 Q개의 줄에는 출발 공항 번호, 도착 공항 번호, 연료의 용량(최대 연료 이동할 수 있는 거리)을 나타내는 세개의 정수 s, t, c가 주어진다 (1 ≤ s, t ≤ N, s ≠ t, 1 ≤ c ≤ 50 000).
각각의 테스트 케이스 첫 번째 줄에 예제와 같이 테스트 케이스의 번호를 출력한다. 뒤이어 한줄씩 s, t, c를 만족하는 최단 비행 경로를 소숫점 셋째 자리 까지 출력한다. 가능한 경로가 존재하지 않다면 "impossible" 을 출력한다.
3 2000 0 0 0 30 30 0 3 2 3 5000 2 3 4000 2 3 3000 2 10000 45 45 225 -45 2 1 2 50000 2 1 50000
Case 1: 4724.686 6670.648 impossible Case 2: impossible impossible
ICPC > World Finals > ACM-ICPC World Finals 2012 J번