Hào dung nham
Đề bài
Mô tả
Những đạo quân chính nghĩa phiền phức lại sắp kéo tới quấy rối vùng đất yên bình của tộc yêu tinh. Xây một bức tường khổng lồ đã không hiệu quả lắm, nên lần này tộc yêu tinh quay về với một biện pháp phòng thủ kinh điển và đáng tin cậy: một con hào chứa đầy dung nham. Họ muốn đào con hào làm ranh giới giữa vùng đất của yêu tinh ở phía bắc và vùng đất của những kẻ thích làm việc tốt ở phía nam, cắt ngang toàn bộ vùng biên giới từ tây sang đông.
Việc này đặt ra một thử thách. Vùng biên giới nhiều đồi, thậm chí có chỗ là núi, trong khi một con hào dung nham phải nằm hoàn toàn trên cùng một độ cao: nếu không, dung nham ở phần cao hơn sẽ chảy xuống và tràn ra khỏi hào ở phần thấp hơn. Vì vậy tộc yêu tinh phải chọn một đường đi nằm hoàn toàn trên cùng một độ cao, nối biên giới phía tây của vùng biên giới với biên giới phía đông của nó. Vì những lý do kinh tế hiển nhiên, họ muốn đường đi này càng ngắn càng tốt.
Đây là lúc bạn xuất hiện. Bạn được cho bản đồ độ cao của vùng biên giới, và nhiệm vụ của bạn là xác định con hào có thể ngắn nhất là bao nhiêu.
Bản đồ là một hình chữ nhật kích thước được tam giác phân hoàn toàn, mọi tam giác đều có diện tích dương. Không có đỉnh nào của một tam giác nằm ở phần trong của một cạnh của tam giác khác. Góc tây nam của bản đồ có tọa độ , trục hướng về phía đông và trục hướng về phía bắc. Hơn nữa, biên phía tây (đoạn thẳng nối và , kể cả hai đầu mút) là một cạnh duy nhất. Tương tự, biên phía đông (giữa hai điểm và ) cũng là một cạnh duy nhất.
Dĩ nhiên bản đồ này chỉ là hình chiếu 2D của địa hình 3D thực tế: mỗi điểm còn có một độ cao . Độ cao tại các đỉnh của tam giác phân được cho trực tiếp trên bản đồ, và mọi độ cao được cho này đôi một khác nhau. Độ cao tại mọi điểm khác được tính bằng nội suy tuyến tính trên tam giác tương ứng. Nói cách khác, địa hình có dạng một tập các mặt tam giác ghép với nhau theo các cạnh chung; các mặt này tương ứng với các tam giác trên bản đồ.
Con hào là một đường đi trong hình chữ nhật, mọi điểm trên đường đi có cùng một độ cao, nối một điểm của biên phía tây với một điểm của biên phía đông.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số bộ test. Tiếp theo là mô tả của bộ test.
Dòng đầu tiên của mỗi bộ test chứa bốn số nguyên , , và , trong đó () là bề rộng của vùng biên giới theo hướng tây sang đông, () là bề rộng theo hướng nam lên bắc, () là số đỉnh, và () là số tam giác của tam giác phân.
Tiếp theo là dòng, dòng thứ chứa ba số nguyên , và (; ; ), là tọa độ và độ cao của đỉnh . Các đỉnh duy nhất có hoặc là bốn góc của hình chữ nhật. Các cặp đôi một khác nhau. Các giá trị đôi một khác nhau.
Mỗi dòng trong dòng tiếp theo chứa ba số nguyên phân biệt , và (), cho biết một tam giác trên bản đồ tạo bởi các đỉnh , và theo thứ tự ngược chiều kim đồng hồ. Các tam giác này tạo thành một tam giác phân hoàn chỉnh của hình chữ nhật . Mỗi đỉnh trong đỉnh thuộc ít nhất một tam giác.
Tổng của mọi bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, nếu có thể xây một con hào dung nham trên cùng một độ cao nối biên phía tây với biên phía đông, in ra độ dài nhỏ nhất của một con hào như vậy, với sai số tuyệt đối hoặc tương đối không quá . Ngược lại, in ra impossible.
Ràng buộc
- ; tổng của mọi bộ test không vượt quá .
- , , .
- , , ; chỉ bốn góc có hoặc ; các cặp đôi một khác nhau; các đôi một khác nhau.
- Các tam giác (cho theo thứ tự ngược chiều kim đồng hồ) tạo thành một tam giác phân hoàn chỉnh của hình chữ nhật; biên phía tây và biên phía đông đều là một cạnh duy nhất.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 6 6 4 2 0 0 1 6 0 4 6 6 3 0 6 2 1 2 3 1 3 4 6 6 4 2 0 0 1 6 0 2 6 6 4 0 6 3 1 2 3 1 3 4 10 6 7 7 6 1 8 10 0 10 10 6 4 2 6 6 0 6 0 4 3 11 0 0 7 2 1 7 2 3 1 3 6 1 3 4 6 6 4 5 5 7 6 7 1 6 |
impossible 6.708203932 15.849260054 |
Bộ thứ nhất: độ cao trên biên tây nằm trong , trên biên đông nằm trong , không có độ cao chung nên không xây được hào. Bộ thứ hai: mọi độ cao đều cho hào dài , chẳng hạn : hào đi từ qua trên đường chéo tới . Bộ thứ ba: hào tối ưu ở độ cao (độ cao của đỉnh tại ), đi từ điểm trên biên tây lên đỉnh rồi tới điểm trên biên đông. |
| 2 4 2 5 4 0 0 1 4 0 2 4 2 4 0 2 5 2 1 3 1 2 5 2 3 5 3 4 5 4 1 5 4 2 5 4 0 0 4 4 0 1 4 2 2 0 2 3 2 1 5 1 2 5 2 3 5 3 4 5 4 1 5 |
4.000000000 impossible |
Cả hai bộ đều là hình chữ nhật chia thành tam giác bởi đỉnh tại . Bộ thứ nhất: ở độ cao (độ cao của đỉnh ), hào là đoạn thẳng từ qua đỉnh tới , dài . Bộ thứ hai: biên tây có độ cao trong , biên đông trong , nên không xây được hào. |
Bình luận