题目详情题解（0）讨论（0）提交记录（0）

AT_abc181_f.[ABC181F] Silver Woods

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 xyxy 平面上，有一条由两条直线 y=−100y=-100 和 y=100y=100 围成的通道。

在该通道内 −100<x<100-100 < x < 100 的部分，钉有 NN 个可以忽略大小的钉子，第 ii 个钉子的坐标为 (xi,yi)(x_i, y_i)。

高桥君可以选择一个实数 r (0<r≤100)r\ (0 < r \leq 100)，并将半径为 rr 的圆的圆心放在 (−109,0)(-10^9, 0)。

之后，他会将这个圆从 (−109,0)(-10^9, 0) 移动到 (109,0)(10^9, 0)。

在移动过程中，圆必须始终保持在通道内，且不能让任何钉子进入圆的内部（可以与钉子相切）。

请你求出能够将圆移动到 (109,0)(10^9, 0) 的最大半径 rr。

输入格式

输入通过标准输入给出，格式如下：

NN
x1 y1x_1\ y_1
x2 y2x_2\ y_2
⋮\vdots
xN yNx_N\ y_N

输出格式

输出能够将圆移动到 (109,0)(10^9, 0) 的最大半径 rr。
如果你的输出与标准答案的绝对误差或相对误差在 10−410^{-4} 以内，则视为正确。

输入输出样例

  • 输入#1

    2
0 -40
0 40

    输出#1

    40

  • 输入#2

    4
0 -10
99 10
0 91
99 -91

    输出#2

    50.5

  • 输入#3

    10
-90 40
20 -30
0 -90
10 -70
80 70
-90 30
-20 -80
10 90
50 30
60 -70

    输出#3

    33.541019662496845446

  • 输入#4

    10
65 -90
-34 -2
62 99
42 -13
47 -84
84 87
16 -78
56 35
90 8
90 19

    输出#4

    35.003571246374276203

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤1001 \leq N \leq 100
  • ∣xi∣,∣yi∣<100|x_i|, |y_i| < 100
  • 若 i≠ji \neq j，则 (xi,yi)≠(xj,yj)(x_i, y_i) \neq (x_j, y_j)

样例解释 1


如图所示，当 r=40r=40 时，可以沿 y=0y=0 将圆从 (−109,0)(-10^9, 0) 移动到 (109,0)(10^9, 0)。在 x=0x=0 时，圆恰好与两个点相切，但没有包含它们在内部，因此没有问题。如果 rr 大于 4040，则无法将圆的圆心移动到 (109,0)(10^9, 0)，因此最大半径为 r=40r=40。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页