poj 2420 A Star not a Tree? 多边形 费马点
题目描述: http://poj.org/problem?id=2420
题目大意: 其实是求n 边形的费马点, 即到n 边形的n 个顶点距离和最小的点,
该题要求计算出最小距离, 并四舍五入.
算法大意: 先拿一个点(该算法用n 个顶点的x, y 坐标和的均值所在的点)去计算距离和
最小值, 然后拿它的四个方向上的点去测试比较哪个点更优, 不断
迭代, 最终得到在精度允许下的费马点.
#include <cstdio>#include <cmath>struct point { double x, y; point() { x = y = 0.0; }};//返回两点间的距离inline double mydistance(point p1, point p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));}//求n 边形的费马点(参数p_fermat), 返回最小距离和double fermat_point(point p[], int n, point& p_fermat) { point u, v; double step = 0.0, curlen, explen, minlen; int i, j, k, idx; bool flag; //u.x = u.y = v.x = v.y = 0.0;//point "构造函数" for(i = 0; i < n; i++) { step += fabs(p.x) + fabs(p.y); u.x += p.x; u.y += p.y; } u.x /= n; u.y /= n; flag = 0; while(step > 1e-10) { for(k = 0; k < 10; step /= 2, k++) for(i = -1; i <= 1; i++) for(j = -1; j <= 1; j++) { v.x = u.x + step * i; v.y = u.y + step * j; curlen = explen = 0.0; for(idx = 0; idx < n; idx++) { curlen += mydistance(u, p); explen += mydistance(v, p); } if(curlen > explen) { u = v; minlen = explen; flag = 1; } } } p_fermat = u; return flag ? minlen : curlen;}int main() { point ploygon, p_fermat; double len; int n; while(scanf("%d", &n) != EOF) { for(int i = 0; i < n; i++) scanf("%lf %lf", &ploygon.x, &ploygon.y); len = fermat_point(ploygon, n, p_fermat); // rounded to the nearest integer /* if(len - (int)len > 0.5) printf("%d\n", (int)(len + 1)); else printf("%d\n", int(len)); */printf("%d\n", int(len + 0.5)); } return 0;}
以上算法参考自代码疯子的博客:http://www.programlife.net/poj-2420-polygon-fermat-point.html
页:
[1]