模拟退火入坑题
Code:
#include#include #include #include #include #include using namespace std;//Mystery_Sky//#define M 1000100#define INF 0x3f3f3f3fstruct node { int x, y, w;}point[M];int n;double Ans_x, Ans_y;double t, Ans = 1e18;int sum_x, sum_y;const double delta = 0.993;inline double dist(double x, double y){ double sum = 0; for(int i = 1; i <= n; i++) { double dx = point[i].x - x; double dy = point[i].y - y; sum += sqrt(dx * dx + dy * dy) * point[i].w; } return sum;}inline void SA(){ double x, y; x = Ans_x, y = Ans_y; t = 2000; while(t > 1e-14) { double new_x = x + ((rand()<<1) - RAND_MAX) * t; double new_y = y + ((rand()<<1) - RAND_MAX) * t; double new_ans = dist(new_x, new_y); double DE = new_ans - Ans; if(DE < 0) { Ans_x = x = new_x, Ans_y = y = new_y; Ans = new_ans; } else if(exp(-DE/t) * RAND_MAX > rand()) x = new_x, y = new_y; t *= delta; }}int main() { srand(19260817); srand(rand()); srand(rand()); scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d%d%d", &point[i].x, &point[i].y, &point[i].w); sum_x += point[i].x; sum_y += point[i].y; } Ans_x = (double) sum_x/n; Ans_y = (double) sum_y/n; SA(); SA(); SA(); printf("%.3lf %.3lf\n", Ans_x, Ans_y); return 0;}