trang chủ / đề bài / icpcwf11_k

Dọn rác

Đề bài

Mô tả

Allied Chute Manufacturers là một công ty sản xuất ống đổ rác. Ống đổ rác là một ống rỗng được lắp đặt trong các tòa nhà, sao cho rác thả vào từ trên đỉnh sẽ rơi xuống và được thu gom ở tầng hầm. Thiết kế ống đổ rác thực ra không hề đơn giản. Tùy theo loại rác mà mọi người dự kiến sẽ thả vào, ống đổ rác cần có kích thước phù hợp. Và vì chi phí sản xuất một ống đổ rác tỉ lệ với kích thước của nó, công ty luôn muốn làm ống nhỏ nhất có thể. Tuy nhiên, chọn đúng kích thước không phải là chuyện dễ.

Ta xét một phiên bản đơn giản hóa hai chiều của bài toán thiết kế ống. Ống đổ rác hướng thẳng đứng xuống dưới và có độ rộng không đổi. Các vật thể được thả vào ống được mô hình hóa bằng các đa giác. Trước khi thả một vật vào ống, có thể xoay vật đó để vừa nhất. Sau khi được thả, vật sẽ rơi theo đường thẳng xuống dưới và không xoay trong khi rơi. Hình dưới đây minh họa một vật được xoay trước rồi mới thả vào ống.

Nhiệm vụ của bạn là tính độ rộng nhỏ nhất của ống đổ rác để một đa giác cho trước có thể lọt qua.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên n (3≤n≤100) là số đỉnh của đa giác mô hình hóa món rác.

n dòng tiếp theo, mỗi dòng chứa hai số nguyên xi và yi (0≤xi,yi≤104) là tọa độ các đỉnh của đa giác theo thứ tự. Các điểm trong cùng một bộ test đôi một phân biệt và các cạnh của đa giác không bao giờ cắt nhau. (Về mặt kỹ thuật, có một ngoại lệ không tránh khỏi là hai cạnh kề nhau có chung đỉnh. Đương nhiên trường hợp này không được coi là cắt nhau.)

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

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test và độ rộng của ống đổ rác nhỏ nhất mà đa giác có thể lọt qua, theo dạng Case i: w (bộ test đánh số từ 1). In độ rộng nhỏ nhất với đúng hai chữ số sau dấu thập phân, làm tròn lên tới bội gần nhất của 1/100. Đáp án lệch không quá 1/100 so với đáp án đã làm tròn đúng vẫn được chấp nhận.

Ràng buộc

  • 3≤n≤100.
  • 0≤xi,yi≤104, mọi tọa độ là số nguyên.
  • Các đỉnh đôi một phân biệt, đa giác không tự cắt.

Ví dụ

Input Output Giải thích
3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0
Case 1: 2.40
Case 2: 14.15
Bộ 1: tam giác vuông cạnh 3,4,5; đặt cạnh huyền áp vào thành ống, độ rộng là đường cao 12/5=2.4. Bộ 2: hình vuông cạnh 200≈14.142, làm tròn lên thành 14.15.
5
0 0
10 0
10 10
5 3
0 10
3
1 1
9 4
2 7
0
Case 1: 10.00
Case 2: 5.27
Bộ 1: đa giác lõm, bao lồi là hình vuông cạnh 10 nên độ rộng là 10. Bộ 2: tam giác có diện tích 22.5; độ rộng nhỏ nhất là đường cao xuống cạnh dài nhất (từ (1,1) đến (9,4), dài 73): 45/73≈5.2669, làm tròn lên thành 5.27.

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