QOJ.ac

QOJ

حد الوقت: 6 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓

#14244. 画圆

الإحصائيات

在第一堂绘画课上,教授要求一名学生在一张大小为 $w \times h$ 单位的矩形纸张上画一个圆。学生坐在鲍威尔图书馆(Powell Library)附近一张舒适的长椅上,正准备开始画画,这时一件糟糕的事情发生了。虽然洛杉矶(LA)从不下雨,但他们偏偏在错误的时间出现在了错误的地方。当他们跑进鲍威尔图书馆时,纸上已经有了 $N$ 个圆形的水滴。

学生无法在属于水滴的任何纸张区域(即水滴的圆形区域内部)上画画,也不允许画一个包含水滴的圆。因此,学生决定在水滴之间画圆,使其不与任何水滴相交,也不包含任何水滴。经过一些简单的计算,他们弄清楚了纸上每个水滴圆的所有坐标和半径。他们还知道,如果画一个更大的圆,教授会给他们更高的分数。这就是为什么他们恳请你帮助他们计算出,在不与任何水滴圆相交的前提下,他们能在纸张中放入的最大圆的半径。

教授在计算中将接受 $10^{-6}$ 的绝对或相对误差。

输入格式

输入的第一行包含两个空格分隔的实数 $w$ 和 $h$($w, h \le 10\,000$),代表矩形纸张的宽度和高度。

第二行包含一个整数 $N$($0 \le N \le 500$),表示水滴圆的数量。

接下来的 $N$ 行,每行包含三个空格分隔的实数 $x_i, y_i, r_i$($0 \le x_i \le w, 0 \le y_i \le h$),代表第 $i$ 个圆的圆心坐标和半径。保证所有圆都严格位于矩形内部,且这些圆可以以任何方式相交或重叠。

输出格式

输出一行,包含一个数字,即可以放入图中的最大圆的半径。你的答案与标准答案的绝对或相对误差不应超过 $10^{-6}$。

样例

输入样例 1

4 2
1
1 1 1

输出样例 1

1.000000

输入样例 2

10 10
3
4 4 2
6 6 2
4 4 1.4

输出样例 2

2.202041

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.