三分 POJ 2420 A Star not a Tree?
发布日期:2021-08-26 18:58:23 浏览次数:11 分类:技术文章

本文共 1431 字,大约阅读时间需要 4 分钟。

 

1 /* 2     题意:求费马点 3     三分:对x轴和y轴求极值,使到每个点的距离和最小 4 */ 5 #include 
6 #include
7 #include
8 #include
9 10 const int MAXN = 1e2 + 10;11 const int INF = 0x3f3f3f3f;12 double x[MAXN], y[MAXN];13 int n;14 15 double sum(double x1, double y1) {16 double res = 0;17 for (int i=1; i<=n; ++i) {18 res += sqrt ((x1 - x[i]) * (x1 - x[i]) + (y1 - y[i]) * (y1 - y[i]));19 }20 return res;21 }22 23 double cal(double x1) {24 int l = 0.0, r = 10000.0;25 for (int i=1; i<=100; ++i) {26 double lmid = (l + r) / 2;27 double rmid = (lmid + r) / 2;28 if (sum (x1, lmid) < sum (x1, rmid)) r = rmid;29 else l = lmid;30 }31 return sum (x1, l);32 }33 34 int main(void) { //POJ 2420 A Star not a Tree?35 //freopen ("POJ_2420.in", "r", stdin);36 37 while (scanf ("%d", &n) == 1) {38 for (int i=1; i<=n; ++i) {39 scanf ("%lf%lf", &x[i], &y[i]);40 }41 42 double l = 0.0, r = 10000.0;43 for (int i=1; i<=100; ++i) {44 double lmid = (l + r) / 2;45 double rmid = (lmid + r) / 2;46 if (cal (lmid) < cal (rmid)) r = rmid;47 else l = lmid;48 }49 printf ("%.0f\n", cal (l));50 }51 52 return 0;53 }

 

转载于:https://www.cnblogs.com/Running-Time/p/4676382.html

转载地址:https://blog.csdn.net/weixin_33894992/article/details/93678352 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【SSH网上商城项目实战24】Struts2中如何处理多个Model请求
下一篇:双拓扑排序 HDOJ 5098 Smart Software Installer

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2025年02月09日 13时40分41秒