Đườ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 tới sân bay phải đi vòng khỏi đường thẳng nối hai sân bay, qua vùng quanh sân bay . Lưu ý máy bay không nhất thiết phải bay tới chính sân bay .

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 tới sân bay trong hình có thể phải dừng ở sân bay (hoặc sức chứa nhiên liệu quá thấp, không đủ bay tới cả sân bay , 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 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 và , trong đó () là số sân bay và () 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 dòng tiếp theo chứa hai số nguyên , (, ) 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ừ 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 (). Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , , (, , ), mô tả một máy bay đi từ sân bay tới sân bay với sức chứa nhiên liệu đủ để bay 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ừ ), 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 và , thỏa mãn ràng buộc nhiên liệu . Độ 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á 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 hoặc thay đổi tới km.
Ràng buộc
- , .
- , , mọi tọa độ là số nguyên; các sân bay đôi một khác vị trí.
- ; , ; .
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 , máy bay bay thẳng một chặng dài km, vòng qua vùng quanh sân bay . Với , chặng đó quá dài nên phải dừng ở sân bay (hai chặng, mỗi chặng km). Với , không bay nổi tới cả sân bay . Bộ 2: hai sân bay ở hai điểm đối xứng tâm của Trái Đất, cách nhau khoảng km, hai vùng an toàn bán kính 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 độ, tức km; hai vùng an toàn phủ kín cung nối chúng nên bay thẳng được khi , còn khi thì không đủ nhiên liệu. Bộ 2: cung nối sân bay và ( km) được phủ bởi vùng an toàn của sân bay ; khi phải dừng ở sân bay , tổng quãng đường dài hơn một chút. |
Bình luận