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