首页 > 代码库 > A Star not a Tree?

A Star not a Tree?

题目链接

  • 题意:
    给n个点,求费马点到各点的距离和
  • 分析:
    费马点直接求即可,用模拟退火即可
    这个方法其实就是默认费马点只有一个,那么就直接求局部最优解即可,不用再以一定概率去接受较差的状态
const double eps = 1e-5;
const int MAXN = 110000;

struct Point
{
    double x, y;
    Point(double x=0, double y=0):x(x),y(y) { }
};

int n;
Point ipt[MAXN];
double dis(Point& a, Point& b)
{
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
double getdis(Point& t)
{
    double ret = 0;
    REP(i, n)
        ret += dis(t, ipt[i]);
    return ret;
}

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int main()
{
//    freopen("in.txt", "r", stdin);
    while (~RI(n))
    {
        Point now = Point(0, 0), pre;
        double Min = 1e20, step = 2000, t;
        REP(i, n)
            scanf("%lf%lf", &ipt[i].x, &ipt[i].y);
        while(step > eps)
        {
            bool ok = true;
            while (ok)
            {
                ok = false;
                REP(i, 4)
                {
                    now.x = pre.x + dx[i] * step;
                    now.y = pre.y + dy[i] * step;
                    if ((t = getdis(now)) < Min)
                    {
                        ok = true;
                        pre = now;
                        Min = t;
                    }
                }
            }
            step /= 2;
        }
        //cout << (int)(Min + 0.5) << endl;
        cout << (int)round(Min) << endl;
    }
    return 0;
}