题目分析

我们需要在平面坐标系上给定 $n$ 个点 $(x_i, y_i)$，并在 $X$ 轴上找到一个点 $x_0$，使得所有点到 $x_0$ 的欧几里得距离的最大值最小。即求：

$$\min_{x_0 \in \mathbb{R}} \left( \max_{1 \leq i \leq n} \sqrt{(x_i - x_0)^2 + y_i^2} \right) $$

解题思路

1. 问题转化

• 目标是最小化所有点到 $x_0$ 的最大距离，等价于最小化函数：$$f(x_0) = \max_{1 \leq i \leq n} \sqrt{(x_i - x_0)^2 + y_i^2} $$
• 由于平方根单调递增，可以简化为最小化：$$g(x_0) = \max_{1 \leq i \leq n} \left( (x_i - x_0)^2 + y_i^2 \right) $$

2. 凸函数性质

• $g(x_0)$ 是由多个二次函数取最大值构成的凸函数，因此其最小值存在且唯一。
• 最优解 $x_0^*$ 满足：向左或向右移动 $x_0$ 都会使最大距离增大（单谷性质）。

3. 三分搜索法

• 利用凸函数的性质，在 $X$ 轴的有效范围内（如 $[\min x_i, \max x_i]$）进行三分搜索：
  1. 初始化左右边界 $l = \min x_i$，$r = \max x_i$。
  2. 每次取两个中间点 $m_1 = l + (r - l)/3$ 和 $m_2 = r - (r - l)/3$。
  3. 计算 $g(m_1)$ 和 $g(m_2)$：
     • 若 $g(m_1) < g(m_2)$，则最小值在 $[l, m_2]$ 区间内，更新 $r = m_2$。
     • 否则，最小值在 $[m_1, r]$ 区间内，更新 $l = m_1$。
  4. 重复直到区间足够小（如 $r - l < 10^{-6}$）。

4. 计算最大距离

• 对于候选点 $x_0$，计算所有点到 $x_0$ 的距离并取最大值：$$\text{max\_dist} = \max_{1 \leq i \leq n} \sqrt{(x_i - x_0)^2 + y_i^2} $$

关键优化

• 三分搜索的收敛性：
  • 每次迭代将搜索区间缩小为原来的 $2/3$，复杂度为 $O(\log (r - l / \epsilon))$。
• 距离计算的优化：
  • 直接计算平方避免开根号，最后再统一开方。

复杂度分析

• 时间复杂度：
  • 三分搜索的迭代次数为 $O(\log (\max x_i - \min x_i / \epsilon))$。
  • 每次迭代需 $O(n)$ 时间计算最大距离。
  • 总复杂度为 $O(n \log (1 / \epsilon))$。
• 空间复杂度：
  • 仅需存储 $n$ 个点的坐标，空间为 $O(n)$。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std ;

const int MAXM = 5e4+5 ;
const int INF = 2e5+5 ;
const double MINM = 1e-10 ;
double x[MAXM], y[MAXM] ;
int n ;

double _distance(int i, double xx){
	double re = y[i]*y[i] + (x[i]-xx)*(x[i]-xx) ;
	return sqrt(re) ;
}
double solve(double p){
	double res = 0.0 ;
	for( int i = 0; i < n; i++ ){
		double temp = _distance(i,p) ;
		if( res < temp ) res = temp ;
	}
	return res ;
}
int main(){
	double l, r ;
	while( scanf("%d",&n) != EOF ){
		if( n == 0 ) break ; 
		l = INF; r = -INF ;
		for( int i = 0; i < n; i++ ){
			scanf("%lf%lf",&x[i],&y[i]) ;
			if( l > x[i] ) l = x[i] ; 
			if( r < x[i] ) r = x[i] ;
		}
		//cout << l << "    " << r << endl ;
		while( r - l >= MINM ){
			double mid1 = (l+r) / 2 ;
			double mid2 = (l+mid1) / 2 ;
			double res1 = solve(mid1) ;
			double res2 = solve(mid2) ;
			if( res1 >= res2 )
				r = mid1 ;
			else
				l = mid2 ;
		}
		printf("%.9lf %.9lf\n",l,solve(l)) ;
	}
	return 0 ;
}