trang chủ / đề bài / icpcwf12_j

Đường bay ngắn nhất

Đề bài

Mô tả

Các chuyến bay thương mại, xét về mặt thống kê, khá an toàn (tính theo số người tử vong trên mỗi hành khách-kilômét, chỉ có bay lên mặt trăng là an toàn hơn). Dù vậy vẫn có những lý do để đặt ra các biện pháp phòng ngừa và quy định an toàn. Một quy định như vậy từ thời kỳ đầu là "quy tắc 60 phút", yêu cầu máy bay hai động cơ trên toàn bộ đường bay luôn phải ở trong phạm vi 60 phút bay tới sân bay phù hợp gần nhất. Đã có nhiều quy tắc tương tự, nhưng về cốt lõi chúng đều giống nhau: đường bay không được đưa máy bay ra xa sân bay gần nhất quá một khoảng cách tối đa cho phép. Vì những hạn chế này, máy bay không phải lúc nào cũng bay thẳng được từ sân bay này tới sân bay khác.

Trong bài này, ta cần tính đường bay ngắn nhất giữa hai sân bay mà vẫn tuân thủ quy tắc khoảng cách tối đa cho phép. Trong hình dưới đây (minh họa bộ test đầu tiên của ví dụ 1), mọi đường bay phải nằm trong ba đường tròn. Do đó máy bay đi từ sân bay 2 tới sân bay 3 phải đi vòng khỏi đường thẳng nối hai sân bay, qua vùng quanh sân bay 1. Lưu ý máy bay không nhất thiết phải bay tới chính sân bay 1.

Mọi việc còn phức tạp hơn vì máy bay chỉ mang được lượng nhiên liệu có hạn, và để đi những quãng đường dài hơn, máy bay có thể phải dừng ở các sân bay trung gian. Như vậy, tùy vào sức chứa nhiên liệu, máy bay đi từ sân bay 2 tới sân bay 3 trong hình có thể phải dừng ở sân bay 1 (hoặc sức chứa nhiên liệu quá thấp, không đủ bay tới cả sân bay 1, khi đó chuyến đi là không thể thực hiện).

Ta dùng các giả thiết đơn giản hóa sau:

  • Bề mặt Trái Đất là một mặt cầu bán kính 6370 km.
  • Cả thời gian lẫn lượng nhiên liệu tiêu thụ đều tỉ lệ thuận với quãng đường bay. Nói cách khác, ta chỉ quan tâm tới tổng quãng đường bay.
  • Chênh lệch quãng đường do máy bay bay ở các độ cao khác nhau là không đáng kể. Do đó, thực chất ta coi máy bay bay dọc theo bề mặt Trái Đất.
  • Máy bay có thể dừng tiếp nhiên liệu ở bao nhiêu sân bay trung gian tùy ý, mỗi lần được đổ đầy bình.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, đọc tới hết file.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên N và R, trong đó N (2≤N≤25) là số sân bay và R (1≤R≤10000) là khoảng cách tối đa cho phép (tính bằng km) tới sân bay gần nhất. Mỗi dòng trong N dòng tiếp theo chứa hai số nguyên φ, θ (0≤φ<360, −90≤θ≤90) lần lượt là kinh độ và vĩ độ của một sân bay, tính bằng độ. Các sân bay được đánh số từ 1 theo thứ tự xuất hiện trong dữ liệu vào. Không có hai sân bay nào ở cùng một vị trí.

Tiếp theo là một dòng chứa số nguyên Q (1≤Q≤100). Mỗi dòng trong Q dòng tiếp theo chứa ba số nguyên s, t, c (1≤s,t≤N, s≠t, 1≤c≤50000), mô tả một máy bay đi từ sân bay s tới sân bay t với sức chứa nhiên liệu đủ để bay c km.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test theo dạng Case i: (bộ test đánh số từ 1), sau đó với mỗi truy vấn in một dòng chứa độ dài (tính bằng km) của đường bay ngắn nhất giữa sân bay s và t, thỏa mãn ràng buộc nhiên liệu c. Độ dài cần chính xác tới ba chữ số sau dấu chấm thập phân (đáp án được chấp nhận nếu sai lệch không quá 0.001 so với đáp án của ban giám khảo). Nếu không có đường bay hợp lệ nào giữa hai sân bay, in từ impossible.

Bạn có thể giả sử rằng đáp án ổn định về mặt số học khi R hoặc c thay đổi tới 0.1 km.

Ràng buộc

  • 2≤N≤25, 1≤R≤10000.
  • 0≤φ<360, −90≤θ≤90, mọi tọa độ là số nguyên; các sân bay đôi một khác vị trí.
  • 1≤Q≤100; 1≤s,t≤N, s≠t; 1≤c≤50000.

Ví dụ

Input Output Giải thích
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
Bộ 1 là hình minh họa ở trên. Với c=5000, máy bay bay thẳng một chặng dài 4724.686 km, vòng qua vùng quanh sân bay 1. Với c=4000, chặng đó quá dài nên phải dừng ở sân bay 1 (hai chặng, mỗi chặng 3335.324 km). Với c=3000, không bay nổi tới cả sân bay 1. Bộ 2: hai sân bay ở hai điểm đối xứng tâm của Trái Đất, cách nhau khoảng 20012 km, hai vùng an toàn bán kính 10000 km không chạm nhau.
2 1000
0 0
10 0
2
1 2 2000
2 1 1000
4 600
0 0
10 0
10 10
5 5
2
1 3 1600
1 3 1500
Case 1:
1111.775
impossible
Case 2:
1568.274
1568.300
Bộ 1: hai sân bay trên xích đạo cách nhau 10 độ, tức 1111.775 km; hai vùng an toàn phủ kín cung nối chúng nên bay thẳng được khi c=2000, còn khi c=1000 thì không đủ nhiên liệu. Bộ 2: cung nối sân bay 1 và 3 (1568.274 km) được phủ bởi vùng an toàn của sân bay 4; khi c=1500 phải dừng ở sân bay 4, tổng quãng đường dài hơn một chút.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0