首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。