QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

#10473. 垃圾清理

Statistics

Allied Chute Manufacturers 是一家制造垃圾槽的公司。垃圾槽是安装在建筑物中的空心管,以便从顶部投入的垃圾能落入地下室并被收集。设计垃圾槽实际上非常复杂。根据人们预期投入的垃圾种类,垃圾槽需要有合适的尺寸。由于制造垃圾槽的成本与其尺寸成正比,公司总是希望建造尽可能小的垃圾槽。然而,选择合适的尺寸可能很困难。

我们将考虑垃圾槽设计问题的二维简化版本。垃圾槽垂直向下,宽度恒定。将被投入垃圾槽的物体建模为多边形。在物体被投入槽中之前,可以对其进行旋转以达到最佳适配。一旦投入,它将沿直线向下移动,且在飞行过程中不会旋转。下图展示了一个物体如何先被旋转以适配垃圾槽。

你的任务是计算允许给定多边形通过的最小垃圾槽宽度。

输入格式

输入包含多个测试用例。每个测试用例以一行包含一个整数 $n$ ($3 \le n \le 100$) 开始,表示建模垃圾物品的多边形的点数。

接下来的 $n$ 行包含整数对 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^4$),按顺序给出多边形的顶点坐标。保证同一测试用例中的所有点互不相同,且多边形边永远不会相交。(从技术上讲,两个相邻边共享公共顶点是不可避免的例外。当然,这不被视为相交。)

最后一个测试用例后跟一行包含单个零。

输出格式

对于每个测试用例,显示其用例编号,后跟该物体可以通过的最小垃圾槽宽度。显示的最小宽度应精确到小数点后两位,向上舍入到 $1/100$ 的最近倍数。与正确舍入答案误差在 $1/100$ 以内的答案将被接受。

请遵循样例输出的格式。

样例

输入 1

3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0

输出 1

Case 1: 2.40
Case 2: 14.15

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.