QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 1024 MB Points totaux : 100

#4668. 寻找长度

Statistiques

平面上有 $n$ 个黑色圆。Alice 计划画一个半径为 $R$ 的蓝色圆,使得没有任何黑色圆的部分在蓝色圆之外。但在 Alice 画圆之前,Bob 计划画一条绿色闭合曲线,使得对于蓝色圆的任何可能位置,蓝色圆的任何部分都不会在绿色曲线之外。

你的任务是求出绿色曲线的最小长度。注意,黑色圆可以与蓝色圆甚至绿色曲线相切,蓝色圆也可以与绿色曲线相切。

输入格式

第一行包含两个整数 $N$ ($1 \le N \le 100$) 和 $R$ ($1 \le R \le 1000$),分别表示黑色圆的数量和蓝色圆的半径。

接下来的 $N$ 行,每行包含三个空格分隔的整数 $x_i, y_i$ 和 $r_i$。前两个整数是第 $i$ 个黑色圆圆心的坐标 ($-500 \le x_i, y_i \le 500$)。第三个整数是该圆的半径 ($1 \le r_i < \min\{R, 500\}$)。没有两个黑色圆重合。

你可以假设如果将 $R$ 改变不超过 $10^{-7}$,答案的变化不会超过 $10^{-3}$。

输出格式

如果无法画出蓝色圆,输出 “Impossible”。否则,输出一个实数,表示绿色曲线的最小可能长度,要求绝对误差或相对误差不超过 $10^{-4}$。

样例

样例输入 1

1 5
0 0 3

样例输出 1

43.982297150257

样例输入 2

4 8
-1 -1 3
-1 -1 1
6 -3 1
2 2 2

样例输出 2

69.138911696387

样例输入 3

2 10
-8 1 3
8 2 4

样例输出 3

Impossible

说明

图片中展示了样例 1 和样例 2。蓝色圆的可能位置由虚线表示。

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.