#include<bits/stdc++.h>

using namespace std;

const int MaxN = 1e3 + 3;
const double EPS = 1e-5;
const double delT = 0.996;

int n;

struct Point
{
    double x, y;
};
Point point[MaxN];
Point point_best;
Point point_last;
double ans_best;
double ans_last;
double w[MaxN];

double dis(Point p1, Point p2)
{
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y))*(p1.y - p2.y);
}

double Energy(Point point_cur)
{
    double ret = 0;
    for (int i = 0; i < n; i++) {
        ret += dis(point[i], point_cur) * w[i];
    }
    return ret;
}

Point move(Point point_cur, double T)
{
    double dx = (1.0 * rand() / RAND_MAX - 0.5) * 2; 
    double dy = (1.0 * rand() / RAND_MAX - 0.5) * 2;
    return {point_cur.x + dx * T, point_cur.y + dy * T};
}

void SA()
{
    double T = 2000;
    while (T > EPS)
    {
        Point point_cur = move(point_last, T);
        double ans_cur = Energy(point_cur);
        double del_ans = ans_cur - ans_last;
        cout << point_cur.x << " " << point_cur.y << " " << T << " " << ans_cur << endl;
        if (del_ans < 0)
        {
            ans_last = ans_cur;
            point_last = point_cur;
        }
        else if (exp(- del_ans / T) * RAND_MAX > rand())
        {
            ans_last = ans_cur;
            point_last = point_cur; 
        }:

        if (ans_cur < ans_best)
        {
            ans_best = ans_cur;
            point_best = point_cur;
        }

        T *= delT; 
    }
}

int main(int argc, char *argv[])
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> point[i].x >> point[i].y >> w[i];
    
    int t=10;
    point_best = point_last = {0, 0};
    ans_best = ans_last = Energy(point_last);
    
    while(t--)
        SA();

    printf("%.3f %.3f", point_best.x, point_best.y);
    return 0;
}

 


评论
还没有评论

添加评论