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[i].x) + fabs(p[i].y);        u.x += p[i].x;        u.y += p[i].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[idx]);                        explen += mydistance(v, p[idx]);                    }                    if(curlen > explen) {                        u = v;                        minlen = explen;                        flag = 1;                    }                }    }    p_fermat = u;    return flag ? minlen : curlen;}int main() {    point ploygon[101], p_fermat;    double len;    int n;    while(scanf("%d", &n) != EOF) {        for(int i = 0; i < n; i++)            scanf("%lf %lf", &ploygon[i].x, &ploygon[i].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