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 () là số đỉnh của đa giác mô hình hóa món rác.
dòng tiếp theo, mỗi dòng chứa hai số nguyên và () 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ố .
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ừ ). 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 . Đáp án lệch không quá so với đáp án đã làm tròn đúng vẫn được chấp nhận.
Ràng buộc
- .
- , 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 ; đặt cạnh huyền áp vào thành ống, độ rộng là đường cao . Bộ 2: hình vuông cạnh , làm tròn lên thành . |
| 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 nên độ rộng là . Bộ 2: tam giác có diện tích ; độ rộng nhỏ nhất là đường cao xuống cạnh dài nhất (từ đến , dài ): , làm tròn lên thành . |
Bình luận