trang chủ / đề bài / icpcwf23_d

Kỳ nghỉ của Carl

Đề bài

Mô tả

Chú kiến Carl đã trở lại! Sau khi đi qua những con đường quanh co (Bài A, World Finals 2004) và lang thang trên các khối bát diện (Bài C, World Finals 2009), đã đến lúc Carl đi nghỉ một chút, đi ngắm cảnh! Còn nơi nào ngắm cảnh tốt hơn đỉnh của những công trình cao, chẳng hạn như kim tự tháp!! Và còn nơi nào có kim tự tháp cao tốt hơn Ai Cập!!! (Thật là hào hứng!!!!!)

Sau khi ngắm cảnh từ đỉnh một kim tự tháp, Carl muốn đi tới đỉnh của một kim tự tháp khác. Vì loài kiến không chịu được nắng nóng, Carl muốn tìm quãng đường ngắn nhất để đi giữa đỉnh của hai kim tự tháp này, biết rằng Carl chỉ có thể đi trên bề mặt của các kim tự tháp và trên mặt phẳng nơi các kim tự tháp được đặt. Về mặt hình học, các kim tự tháp là hình chóp tứ giác đều, nghĩa là đáy là một hình vuông và đỉnh nằm thẳng phía trên tâm của hình vuông đáy.

Hình trên minh họa hai kim tự tháp của ví dụ thứ nhất (nhìn từ trên xuống). Đường màu đen là đường đi ngắn nhất giữa hai đỉnh.

Dữ liệu vào

Dòng đầu tiên chứa năm số nguyên x1,y1,x2,y2,h. Bốn số x1,y1,x2,y2 (−105≤x1,x2,y1,y2≤105 và (x1,y1)≠(x2,y2)) xác định một cạnh đáy của kim tự tháp thứ nhất, trong đó thân kim tự tháp nằm ở phía bên trái của vectơ có hướng đi từ (x1,y1) tới (x2,y2). Số h (1≤h≤105) là chiều cao của kim tự tháp.

Dòng thứ hai mô tả kim tự tháp thứ hai theo cùng định dạng.

Phần giao của hai đáy kim tự tháp có diện tích bằng 0.

Dữ liệu ra

In ra quãng đường nhỏ nhất Carl phải đi giữa đỉnh của hai kim tự tháp. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá 10−6.

Ràng buộc

  • −105≤x1,y1,x2,y2≤105, (x1,y1)≠(x2,y2).
  • 1≤h≤105.
  • Hai đáy hình vuông có phần giao diện tích bằng 0 (có thể chạm nhau).

Ví dụ

Input Output Giải thích
0 0 10 0 4
9 18 34 26 42
60.866649532 Đáy thứ nhất là hình vuông [0,10]×[0,10], đỉnh ở (5,5) cao 4. Đáy thứ hai có các đỉnh (9,18), (34,26), (26,51), (1,43), đỉnh ở (17.5,34.5) cao 42. Đường ngắn nhất đi xuống mặt bên phía trên của kim tự tháp thứ nhất, đi trên mặt đất tới góc (9,18) của đáy thứ hai, rồi đi lên theo cạnh bên tới đỉnh (như trong hình).
0 0 8 0 3
0 8 8 8 3
10.0 Hai đáy [0,8]×[0,8] và [0,8]×[8,16] chung cạnh y=8. Mỗi mặt bên chứa cạnh này có đường cao từ đỉnh dài 32+42=5, nên đi thẳng xuống trung điểm cạnh chung rồi đi lên: 5+5=10.
0 0 8 0 2
8 8 16 8 2
12.0 Hai đáy chỉ chạm nhau tại góc (8,8). Cạnh bên từ mỗi đỉnh tới góc này dài 22+42+42=6, nên đi theo hai cạnh bên: 6+6=12.

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