QOJ.ac

QOJ

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

#3448. 断层合成

Statistics

断层扫描(Tomosynthesis)是一种医学成像方式,通过在有限角度范围内从不同方向拍摄的一组 X 射线图像,利用算法获取 3D 数据集。通常,较大的角度范围能提供更好的重建效果,但获取难度也更大。Arvid 正在研究一种用于获取 3D 图像的重建算法,但到目前为止,当输入图像中存在重叠结构时,该算法似乎无法正常工作。他首先要重建的样本是一个测试对象,由一组平行、等长、直径各异的圆柱体组成,这些圆柱体将绕其轴线旋转。

图 D.1:左侧为样例输入 1 中测试对象的横截面。上方的投影不可接受,因为两个较大的圆柱体发生了重叠。在下方的投影中,没有圆柱体发生重叠,因此该方向及其周围的一定角度范围是可行的。右侧为同一测试对象的侧视图。

撇开他的算法在实际中可能无法工作这一点不谈,Arvid 向你寻求帮助。在任何图像中都没有圆柱体发生重叠的情况下,测试对象可以成像的最大角度范围是多少?图像是结构垂直于圆柱体轴线的平面投影。

输入格式

输入的第一行包含一个整数 $2 \le N \le 100$,表示构成测试对象的圆柱体数量。接下来有 $N$ 行,每行包含三个浮点数 $x, y$ 和 $r$,分别表示圆柱体中心的 $x$ 坐标、$y$ 坐标以及该圆柱体的半径。坐标范围为 $-1\,000 \le x, y \le 1\,000$,半径范围为 $0 < r \le 1\,000$。没有任何圆柱体接触或重叠。

输出格式

输出一个数字,表示在没有圆柱体发生重叠的情况下,投影方向的最大连续范围的大小(以弧度为单位)。如果不存在这样的角度,则输出 $0$。你的答案的绝对误差应不超过 $10^{-8}$。

样例

样例输入 1

3
-1 -1 0.5
1 -1 0.25
1 1 1

样例输出 1

0.511268019

样例输入 2

2
0 0 1
2 2 1

样例输出 2

1.570796327

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.