POJ-2420 A Star not a Tree? 计算几何 模拟退火

POJ-2420 A Star not a Tree?

题意: 给定n个点, 找到一个点p. 使得p到所有点的距离之和最小.
分析: 模拟退火随机产生圆心坐标, 跑一遍模拟退火就行, 这题n的范围是100, 莫名其妙re, 开1000就ac了.
代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;const int MAXN = 1111;const double eps = 1e-8;
const double pi = acos(-1);
const double inf = 0x3f3f3f3f;
struct Point {
    double x, y;Point() {
    }Point(double _x, double _y) {
    x = _x;y = _y;}double distance(Point b) {
     return hypot(x - b.x, y - b.y); }
};
Point p[MAXN];
int n;
Point ans;
double Rand() {
     return (double)rand() / RAND_MAX; }double getdis(Point b) {
    double res = 0;for (int i = 0; i < n; i++) {
    res += b.distance(p[i]);}return res;
}
int main() {
    srand(0);while (scanf("%d", &n) != EOF) {
    ans.x = 0, ans.y = 0;for (int i = 0; i < n; i++) {
    scanf("%lf%lf", &p[i].x, &p[i].y);ans.x += p[i].x;ans.y += p[i].y;}ans.x /= n;ans.y /= n;double t = 100000;double res = getdis(ans);Point nxt;while (t > eps) {
    nxt.x = ans.x + t * (Rand() * 2 - 1);nxt.y = ans.y + t * (Rand() * 2 - 1);double dis = getdis(nxt);if (res > dis) {
    res = dis;ans = nxt;}t *= 0.97;}printf("%.0f", res);}return 0;
}