解题思路

设需覆盖的点数 $k=\lceil n/2\rceil$。对答案半径 $r$ 二分，判断能否在横轴或纵轴上放置圆心，使覆盖点数不少于 $k$。

给定半径 $r$：

• 圆心在横轴 $(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]$。
• 圆心在纵轴 $(0,c)$：类似地，$c$ 落在 $[y_i-d_i,y_i+d_i]$，其中 $d_i=\sqrt{r^2-x_i^2}$。