trang chủ / đề bài / icpcwf04_b

Sân bay trực thăng

Đề bài

Mô tả

Trong thời đại hối hả ngày nay, các công ty đầu tư xây sân bay trực thăng để rút ngắn thời gian di chuyển của những giám đốc bận rộn. Sân bay trực thăng thường là một bãi đáp hình tròn, xây trên mái toà nhà trụ sở của công ty.

Bạn cần viết chương trình tìm bán kính lớn nhất của một bãi đáp hình tròn có thể xây trên mái bằng của một toà nhà, mái có dạng một đa giác đơn. Vì đây mới là giai đoạn thiết kế, chương trình chỉ cần tìm bán kính của bãi đáp. Bãi đáp phải nằm trọn trong mái (được phép chạm vào biên của mái). Với mái trong hình dưới đây, bán kính lớn nhất của bãi đáp là 10.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, mỗi bộ test gồm hai dòng.

  • Dòng thứ nhất chứa một số nguyên chẵn n (4≤n≤20): số cạnh của mái.
  • Dòng thứ hai chứa n cặp có dạng m d, trong đó m là số nguyên (1≤m≤50) và d là một chữ cái U, R, D hoặc L. Coi mái được vẽ trên mặt phẳng toạ độ Descartes, m là độ dài một đoạn biên của mái và d là hướng của đoạn đó khi đi quanh mái ngược chiều kim đồng hồ: U, R, D, L lần lượt là đi lên, sang phải, đi xuống, sang trái.

Các đoạn biên của mái song song với các trục toạ độ và được cho theo thứ tự ngược chiều kim đồng hồ. Điểm xuất phát là gốc toạ độ (0,0).

Sau bộ test cuối cùng là một dòng chứa số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test (bắt đầu từ 1) và một số thực làm tròn đến đúng hai chữ số sau dấu thập phân là bán kính của bãi đáp, theo đúng định dạng của ví dụ. In một dòng trống giữa hai bộ test liên tiếp.

Ràng buộc

  • n chẵn, 4≤n≤20; 1≤m≤50.
  • Hai đoạn biên liên tiếp (kể cả đoạn cuối và đoạn đầu) luôn vuông góc với nhau; đường đi khép kín về (0,0).
  • Mái là đa giác đơn: hai đoạn biên không kề nhau không có điểm chung.
  • Mỗi file có không quá 200 bộ test.
  • Bán kính đúng của mỗi bộ test cách mọi giá trị có chữ số thập phân thứ ba đúng bằng 5 (trường hợp làm tròn nước đôi) ít nhất 10−6.

Ví dụ

Input Output Giải thích
4
2 R 2 U 2 L 2 D
10
10 R 10 U 10 L 10 U 10 R 5 U 30 L 20 D 20 R 5 D
0
Case Number 1 radius is: 1.00

Case Number 2 radius is: 10.00
Bộ test 1: mái là hình vuông cạnh 2. Bộ test 2: mái trong hình vẽ, bãi đáp tâm (−10,15) chạm các cạnh x=−20, x=0, y=5 và y=25.
4
1 R 50 U 1 L 50 D
6
4 R 2 U 2 L 2 U 2 L 4 D
8
3 R 1 U 2 R 2 U 2 L 3 U 3 L 6 D
0
Case Number 1 radius is: 0.50

Case Number 2 radius is: 1.17

Case Number 3 radius is: 1.67
Ví dụ tự thêm. Bộ test 1: hình chữ nhật 1×50. Bộ test 2: hình chữ L (hình vuông 4×4 bỏ góc 2×2 phía trên bên phải), bãi đáp chạm hai cạnh x=0, y=0 và góc lõm (2,2), bán kính 4−22≈1,1716. Bộ test 3: bãi đáp chạm cạnh x=0 và hai góc lõm (3,1), (3,3), bán kính 5/3.

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