解题思路

二分半径 + 扫描线

• 思路概览：将答案 $r$ 用二分搜索，在每个候选半径上判断能否在 $x$ 轴或 $y$ 轴上放置圆心，使得被覆盖点数 $\ge k$，其中 $k=\lceil n/2\rceil$。

• 可行性检查：

  1. 对给定半径 $r$，分别在两条轴上判断：

     • 横轴情况（axis=0）：圆心 $(c,0)$ 覆盖点 $(x_i,y_i)$ 的条件是 $|y_i|\le r$ 且 $|c - x_i|\le \sqrt{r^2 - y_i^2}$，从而得到在 $c$ 轴上的区间 $[x_i - d_i,x_i + d_i]$。

题目内容

在平面上给定$n$个二维点，其坐标分别为$(x_i, y_i)(1≤i≤n)$。

现在需要在坐标平面上以某一点$C$为圆心画一个圆，且使得该圆能够覆盖不少于该圆心必须位于坐标轴上。

请你找到一个最小的半径$r$，使得该圆能过覆盖不少于$[n/2]$个给定点，并输出这个最小半径。

【名词解释】

• 坐标轴：包含$x$轴和$y$轴。轴表示形如$(x，0)$的所有点；$y$轴表示形如$(0，y)$的所有点。

• 覆盖：若点$P$到圆心$C$的欧氏距离不超过圆的半径，则称该圆覆盖点$P$。

输入描述

第一行输入一个整数$n(2≤n≤10^5)$，表示点的数量。

接下来$n$行，每行输入两个整数$x_i,y_i(-10^5≤x_i,y_i≤10^5)$,表示第$i$个点的坐标。

输出描述

输出一个实数，表示能够覆盖至少$[n/2]$个给定点的、以坐标轴上某点为圆心的最小圆的半径。

由于实数计算可能产生误差，当误差的量级不超过$10^{-6}$时，您的答案都将被接受。具体来说，设您的输出为$a$，标准答案为$b$，当且仅当$\frac{|a-b|}{max(1,|b|)}≤10^{-6}$时，您的答案将被接受。

输入

2
0 0
3 4

输出

0.0000000000

说明

在这个样例中，$n=2，[n/2]=1$；我们可以选择圆心$(0,0)$，半径$0$，覆盖点$(0,0)$。

样例2

输入

4
1 0
2 0
3 0
100 100

输出

0.5000000000

说明

在这个样例中，$n=4，[n/2]=2$；我们可以选择圆心$(1.5,0)$，半径$0.5$，即可覆盖点$(1,0)$和$(2,0)$。