首页 > 代码库 > bzoj3680 吊打XXX
bzoj3680 吊打XXX
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3680
【题解】
模拟退火
getdis瞎推推,猜猜就猜出来了吧。。
前面没看n的范围设N=20, T=20作死
改成T=5,N=8就10s刚好过了
# include <math.h> # include <stdio.h> # include <stdlib.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e4 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, w[M]; double minx, miny, maxx, maxy; struct P { double x, y; double dis; P() {} P(double x, double y, double dis) : x(x), y(y), dis(dis) {} }p[M]; namespace SA { const int RAD = 1000; const int T = 5, N = 8; const double eps = 1e-3, DEC = 0.9, ACCEPT_DEC = 0.5; inline double rand01() { return rand() % (RAD + 1) / (1.0 * RAD); } inline double getdis(double x, double y) { double ret = 0; for (int i=1; i<=n; ++i) { ret += sqrt((p[i].x-x)*(p[i].x-x)+(p[i].y-y)*(p[i].y-y)) * w[i]; } return ret; } inline P randpoint(double xl, double yl, double xr, double yr) { double x = (xr-xl) * rand01() + xl, y = (yr-yl) * rand01() + yl; return P(x, y, getdis(x, y)); } P res[N + 5]; inline P main() { double temper = sqrt(1.0 * (maxx-minx)*(maxx-minx) + 1.0 * (maxy-miny)*(maxy-miny)), accept = 0.6; for (int i=1; i<=N; ++i) res[i] = randpoint(minx, miny, maxx, maxy); while(temper > eps) { for (int i=1; i<=N; ++i) for (int j=1; j<=T; ++j) { P t = randpoint(max(minx, res[i].x-temper), max(miny, res[i].y-temper), min(maxx, res[i].x+temper), min(maxy, res[i].y+temper)); if(t.dis < res[i].dis) res[i] = t; else if(rand01() <= accept) res[i] = t; } temper *= DEC; accept *= ACCEPT_DEC; } P ans = res[1]; for (int i=2; i<=N; ++i) if(ans.dis > res[i].dis) ans = res[i]; return ans; } } int main() { minx = miny = 1e9, maxx = maxy = -1e9; cin >> n; for (int i=1, x, y; i<=n; ++i) { scanf("%d%d%d", &x, &y, w+i); minx = min(minx, (double)x); maxx = max(maxx, (double)x); miny = min(miny, (double)y); maxy = max(maxy, (double)y); p[i] = P((double)x, (double)y, 0); } P ans = SA::main(); printf("%.3lf %.3lf\n", ans.x, ans.y); return 0; }
bzoj3680 吊打XXX
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。