🧠 题解（Solution）

✅ 本质分析

本题目标是：寻找一个点（hub的位置），使其到所有已知电脑的欧几里得距离之和最小。

这是几何中的一个经典问题，称为费马点问题（Fermat Point / Geometric Median）。

✅ 解法思路：几何中位点（Geometric Median）

设 $P = {p_1, p_2, ..., p_n}$ 为电脑的坐标集合；

求一点 $h$，使得以下目标函数最小：

Total ( ℎ )

∑ 𝑖

1 𝑛 dist ( ℎ , 𝑝 𝑖 ) Total(h)= i=1 ∑ n ​ dist(h,p i ​ ) 其中 $\text{dist}(a, b)$ 为欧几里得距离。

✅ 求解方法：Weiszfeld 算法（或模拟退火）

本题最优解可以使用Weiszfeld 算法或模拟退火求解。

但由于点数 $N \leq 100$，我们可以采用如下做法：

在平面内使用模拟退火搜索几何中位点，然后四舍五入输出总距离。

✅ 距离函数（欧几里得）定义

若 $a = (x_1, y_1)$，$b = (x_2, y_2)$，则：

dist ( 𝑎 , 𝑏 )

( 𝑥 1 − 𝑥 2 ) 2 + ( 𝑦 1 − 𝑦 2 ) 2 dist(a,b)= (x 1 ​ −x 2 ​ ) 2 +(y 1 ​ −y 2 ​ ) 2

​

✅ 示例分析

输入中有 4 台电脑，分别在矩形的四个角上：

$(0, 0)$

$(0, 10000)$

$(10000, 10000)$

$(10000, 0)$

最优 hub 放在中心点 $(5000, 5000)$，此时每台电脑到 hub 的距离为：

( 5000 2 + 5000 2 )

5 × 10 7 ≈ 7071.07 (5000 2 +5000 2 ) ​

5×10 7

​ ≈7071.07 总电缆长度约为：

4 × 7071.07 ≈ 28284.27 ⇒ 28284 4×7071.07≈28284.27⇒ 28284 ​

✅ 算法复杂度

模拟退火的复杂度约为 $O(N \cdot T)$，其中 $T$ 为温度迭代次数，适用于 $N \leq 100$ 的情况。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
//#define ivorysi
#define MAXN 105
#define eps 1e-8
#define pb push_back
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N;
struct Point {
	db x,y;
}P[MAXN];
inline db o (db x) {return x * x;}
db GetSum(Point s) {
	db res = 0;
	for(int i = 1 ; i <= N ; ++i) {
		res += sqrt(o(s.x - P[i].x) + o(s.y - P[i].y)); 
	}
	return res;
}
void Init() {
	for(int i = 1 ; i <= N ; ++i) scanf("%lf%lf",&P[i].x,&P[i].y);
}
u32 Rand() {
	static u32 x = 1736382156;
	return x += x << 2 | 1;
}
db Range_rand() {
	return (db)(Rand() % 10000) / 10000;//生成一个[0,1)之内的概率
}
void Solve() {
	db delta = 0.98,T = 1000;
	db ans = GetSum(P[1]);
	Point s = P[1];//选一个点当做初始点
	while(T > eps) {
		db tmp = 1e18;
		Point t;
		for(int i = 0 ; i < 4 ; ++i) {
			Point z;
			z.x = s.x + dx[i] * T;z.y = s.y + dy[i] * T;
			db x = GetSum(z);
			if(x < tmp) tmp = x,t = z;
		}
		//找四个方向里最小的那个尝试更新答案
		if(tmp < ans) {
			ans = tmp;
			s = t;
		}
		else {//以一定的概率接受这个解
			if(exp((ans - tmp) / T) > Range_rand()) {
				ans = tmp;
				s = t;
			}
		}
		T = delta * T;//降温
	}
	printf("%.0f",ans);
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	while(scanf("%d",&N) != EOF && N) {
		Init();
		Solve();
	}
}