题目传送门
/*
题意:求费马点
三分:对x轴和y轴求极值,使到每个点的距离和最小
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
const int MAXN = 1e2 + ;
const int INF = 0x3f3f3f3f;
double x[MAXN], y[MAXN];
int n;
double sum(double x1, double y1) {
double res = ;
for (int i=; i<=n; ++i) {
res += sqrt ((x1 - x[i]) * (x1 - x[i]) + (y1 - y[i]) * (y1 - y[i]));
}
return res;
}
double cal(double x1) {
int l = 0.0, r = 10000.0;
for (int i=; i<=; ++i) {
double lmid = (l + r) / ;
double rmid = (lmid + r) / ;
if (sum (x1, lmid) < sum (x1, rmid)) r = rmid;
else l = lmid;
}
return sum (x1, l);
}
int main(void) { //POJ 2420 A Star not a Tree?
//freopen ("POJ_2420.in", "r", stdin);
while (scanf ("%d", &n) == ) {
for (int i=; i<=n; ++i) {
scanf ("%lf%lf", &x[i], &y[i]);
}
double l = 0.0, r = 10000.0;
for (int i=; i<=; ++i) {
double lmid = (l + r) / ;
double rmid = (lmid + r) / ;
if (cal (lmid) < cal (rmid)) r = rmid;
else l = lmid;
}
printf ("%.0f\n", cal (l));
}
return ;
}