你正在为一家设计可爱、有趣的机器人吸尘器的公司工作。从高层逻辑来看,机器人的行为分为三种模式:
- 探索
- 吸尘
- 疯狂杀戮
不幸的是,虽然消费者测试显示后两种模式运行完美,但探索模式仍然存在漏洞。你被指派负责调试工作。
在探索模式开始时,机器人被放置在一个凸多边形房间内。它配备了传感器,应该能告知它所有墙壁的位置。你的任务是编写一个程序来验证这些读数是否正确。为此,机器人需要物理接触房间内的每一面墙。
你的问题是:给定一个具有 $N$ 面墙的凸多边形房间以及内部的一个起始点 $P$,确定一条接触每一面墙并最终返回 $P$ 的最短路径。接触一个角被视为同时接触了该角所连接的两面墙。
输入格式
每个测试用例的第一行包含多边形的顶点数 $N$ ($3 \le N \le 100$) 以及机器人起始点 $P$ 的整数坐标 $P_x$ 和 $P_y$ ($-10\,000 \le P_x, P_y \le 10\,000$)。接下来有 $N$ 行,每行包含两个整数 $x, y$ ($-10\,000 \le x, y \le 10\,000$),定义了多边形的一个顶点。顶点按逆时针顺序给出,所有内角均小于 180 度,多边形不自交,且机器人的起始点严格位于多边形内部。
输出格式
对于每个测试用例,显示用例编号以及所需路径的长度,精确到小数点后两位。
样例
输入 1
4 0 0 -1 -1 1 -1 1 1 -1 1 3 10 1 0 0 30 0 0 20
输出 1
Case 1: 5.66 Case 2: 36.73