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à .

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 (): số cạnh của mái.
- Dòng thứ hai chứa cặp có dạng
m d, trong đó là số nguyên () và là một chữ cáiU,R,DhoặcL. Coi mái được vẽ trên mặt phẳng toạ độ Descartes, là độ dài một đoạn biên của mái và là hướng của đoạn đó khi đi quanh mái ngược chiều kim đồng hồ:U,R,D,Llầ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ạ độ .
Sau bộ test cuối cùng là một dòng chứa số .
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ừ ) 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
- chẵn, ; .
- 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ề .
- 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á 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 (trường hợp làm tròn nước đôi) ít nhất .
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 . Bộ test 2: mái trong hình vẽ, bãi đáp tâm chạm các cạnh , , và . |
| 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 . Bộ test 2: hình chữ L (hình vuông bỏ góc phía trên bên phải), bãi đáp chạm hai cạnh , và góc lõm , bán kính . Bộ test 3: bãi đáp chạm cạnh và hai góc lõm , , bán kính . |
https://oj.chuyentin.pro/problem/icpcwf04_b
Bình luận