三分 POJ 2420 A Star not a Tree?

题目传送门

 /*
题意:求费马点
三分:对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 ;
}
上一篇:Sublime Text3下如何快速搭建开发环境


下一篇:ubuntu dpkg 依赖问题处理