QOJ.ac

QOJ

実行時間制限: 3 s メモリ制限: 512 MB 満点: 100

#10446. 客房服务

統計

你正在为一家设计可爱、有趣的机器人吸尘器的公司工作。从高层逻辑来看,机器人的行为分为三种模式:

  1. 探索
  2. 吸尘
  3. 疯狂杀戮

不幸的是,虽然消费者测试显示后两种模式运行完美,但探索模式仍然存在漏洞。你被指派负责调试工作。

在探索模式开始时,机器人被放置在一个凸多边形房间内。它配备了传感器,应该能告知它所有墙壁的位置。你的任务是编写一个程序来验证这些读数是否正确。为此,机器人需要物理接触房间内的每一面墙。

你的问题是:给定一个具有 $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

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.