trang chủ / đề bài / icpcwf25_g

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 w×ℓ đượ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 độ (0,0), trục x hướng về phía đông và trục y hướng về phía bắc. Hơn nữa, biên phía tây (đoạn thẳng nối (0,0) và (0,ℓ), 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 (w,0) và (w,ℓ)) 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 (x,y) còn có một độ cao z. Độ 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 t (1≤t≤10000), số bộ test. Tiếp theo là mô tả của t bộ test.

Dòng đầu tiên của mỗi bộ test chứa bốn số nguyên w, ℓ, n và m, trong đó w (1≤w≤106) là bề rộng của vùng biên giới theo hướng tây sang đông, ℓ (1≤ℓ≤106) là bề rộng theo hướng nam lên bắc, n (4≤n≤50000) là số đỉnh, và m (n−2≤m≤2n−6) là số tam giác của tam giác phân.

Tiếp theo là n dòng, dòng thứ i chứa ba số nguyên xi, yi và zi (0≤xi≤w; 0≤yi≤ℓ; 0≤zi≤106), là tọa độ và độ cao của đỉnh i. Các đỉnh duy nhất có xi=0 hoặc xi=w là bốn góc của hình chữ nhật. Các cặp (xi,yi) đôi một khác nhau. Các giá trị zi đôi một khác nhau.

Mỗi dòng trong m dòng tiếp theo chứa ba số nguyên phân biệt a, b và c (1≤a,b,c≤n), cho biết một tam giác trên bản đồ tạo bởi các đỉnh a, b và c 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 [0,w]×[0,ℓ]. Mỗi đỉnh trong n đỉnh thuộc ít nhất một tam giác.

Tổng n của mọi bộ test không vượt quá 50000.

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á 10−6. Ngược lại, in ra impossible.

Ràng buộc

  • 1≤t≤10000; tổng n của mọi bộ test không vượt quá 50000.
  • 1≤w,ℓ≤106, 4≤n≤50000, n−2≤m≤2n−6.
  • 0≤xi≤w, 0≤yi≤ℓ, 0≤zi≤106; chỉ bốn góc có xi=0 hoặc xi=w; các cặp (xi,yi) đôi một khác nhau; các zi đô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 [1,2], trên biên đông nằm trong [3,4], không có độ cao chung nên không xây được hào. Bộ thứ hai: mọi độ cao h∈[2,3] đều cho hào dài 35=45≈6,708, chẳng hạn h=2,5: hào đi từ (0; 4,5) qua (3; 3) trên đường chéo tới (6; 1,5). Bộ thứ ba: hào tối ưu ở độ cao 6 (độ cao của đỉnh 4 tại (2,6)), đi từ điểm (0,67) trên biên tây lên đỉnh 4 rồi tới điểm (10,4) 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 4×2 chia thành 4 tam giác bởi đỉnh 5 tại (2,1). Bộ thứ nhất: ở độ cao 3 (độ cao của đỉnh 5), hào là đoạn thẳng y=1 từ (0,1) qua đỉnh 5 tới (4,1), dài 4. Bộ thứ hai: biên tây có độ cao trong [3,4], biên đông trong [1,2], nên không xây được hào.

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