UVA10228 A Star not a Tree?
题意翻译
给定一个N边形所有顶点坐标x,y,求其费马点到所有顶点距离和
费马点是指到多边形所有顶点距离和最小的点
输入
第一行为T, T组数据
第二行正整数N,其后N行,每行两个整数x,y。
输出
每行一个数,为所求距离和,精确到整数(每组数据要多输出一个换行,最后一组不用)
Translated by @BeyondOI
输入输出样例
输入 #1
1
4
0 0
0 10000
10000 10000
10000 0
输出 #1
28284
这道题做法有三分和模拟退火,我用的是模拟退火。
我的模拟退火板子(感谢Tethys的友情支持):
void SA() {
double temp = 3000;
double x = ax , y = ay;
while(temp > eps) {
double x1 = x + ((rand() << 1) - RAND_MAX) * temp;
double y1 = y + ((rand() << 1) - RAND_MAX) * temp;
double now_ans = calc(x1, y1);
double del = now_ans - ans;
if(del < 0) {
ax = x1, ay = y1;
x = x1, y = y1;
ans = now_ans;
}
else
if(exp(- del / temp) * RAND_MAX > rand())
x = x1, y = y1;
temp *= dwtem;
}
}
temp:温度;
dwtem :每次降温多少;
del :\(\Delta\)E;
公式:\(P(\Delta E) = e ^ {\frac{\Delta E}{T}}\);
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 105;
const double eps = 1e-12;
const double dwtem = 0.996;
int n, T;
double ax, ay, ans, sumx, sumy;
struct node { double x, y; } a[N];
double calc(double x, double y) {
double res = 0;
for(int i = 1;i <= n; i++)
res += sqrt((x - a[i].x) * (x - a[i].x) + (y - a[i].y) * (y - a[i].y));
return res;
}
void SA() {
double temp = 3000;
double x = ax , y = ay;
while(temp > eps) {
double x1 = x + ((rand() << 1) - RAND_MAX) * temp;
double y1 = y + ((rand() << 1) - RAND_MAX) * temp;
double now_ans = calc(x1, y1);
double del = now_ans - ans;
if(del < 0) {
ax = x1, ay = y1;
x = x1, y = y1;
ans = now_ans;
}
else
if(exp(- del / temp) * RAND_MAX > rand())
x = x1, y = y1;
temp *= dwtem;
}
}
int main() {
srand(1e9 + 7);
T = read();
for(int i = 1;i <= T; i++) {
n = read();
sumx = sumy = 0; ans = 1e11;
for(int j = 1;j <= n; j++) {
scanf("%lf %lf", &a[j].x, &a[j].y);
sumx += a[j].x; sumy += a[j].y;
}
ax = sumx / n; ay = sumy / n;
for(int j = 1;j <= 5; j++) SA();
printf("%.0lf\n", ans);
if(i != T) printf("\n");
}
return 0;
}
(感觉模拟退火好迷呀,都是rand)