在二维平面上有 n 个点，第 i 个点的坐标为 (xi,yi)。请你找出一个点，使得该点到这 n个点的距离之和最小。该点可以选择在平面中的任意位置，甚至与这 n个点的位置重合。
输入格式
第一行包含一个整数 n。接下来 n行，每行包含两个整数 xi,yi，表示其中一个点的位置坐标。
输出格式
输出最小距离和，答案四舍五入取整。
数据范围
1≤n≤100,0≤xi,yi≤10000
输入样例：
4 0 0 0 10000 10000 10000 10000 0 
输出样例：
28284
详解：代码注释（提前了解模拟退火算法的过程）
AC代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<utility> #include<stdlib.h> #include<stdio.h> using namespace std; typedef long long ll; #define x first //给pair的两个成员起别名 #define y second #define N 110 //最大范围 typedef pair<double, double> pdd; int n; pdd p[N]; //存坐标的变量 double ans = 1e9; //存答案的变量 double dist(pdd a, pdd b) //计算两点距离 { double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx*dx+dy*dy); } double s_dist(pdd a) //将随机到的一个点与输入的点计算距离 { double ret = 0; //存随机点的距离 for (int i = 0; i < n; i++)ret += dist(p[i], a); ans = min(ret, ans); //与答案比较 return ret; } double rand(int a, int b) //生成（a,b）的随机数 { return (double)rand() / RAND_MAX * (b - a) + a; } void th() //模拟退火 { pdd a(rand(0, 1e4), rand(0, 1e4)); //随机一个初始点 for (double i = 1e4; i >= 1e-4; i *= 0.99) //退火 for(初始温度;最低温度;衰减因子) { pdd temp(rand(a.x-i,a.x+i), rand(a.y-i,a.y+i)); //新随机点 double sub = s_dist(temp) - s_dist(a); //比较两点 //sub<0时，新点较小，所以必然执行a=temp (exp(-x)>1>rand(0,1))，sub>0时可能执行a=temp if (exp(-sub / i) > rand(0, 1))a = temp; } } int main() { cin >> n; for (int i = 0; i < n; i++)cin >> p[i].x >> p[i].y; for (int i = 0; i < 100; i++)th(); //进行100次模拟退火 printf("%.0f", ans); return 0; }
