题目大意
给定$n$个点, 求一个点使得这个点到所有$n$个点的距离最小，输出距离（保留整数）
题解
计算几何什么的我不会o((⊙﹏⊙))o
那我们就来随机化吧(￣▽￣)~*
按照模拟退火的套路来：每次随机一个点，判他是不是比答案更优，如果更优的话就更新，否则就以一定的几率接受该解。直到稳定在最优解为止。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
const int MaxN = 200;
const double delta = 0.995;
int n;
int x[MaxN], y[MaxN];
double ansx, ansy;
inline double calc(double nx, double ny)
{
double tmp = 0;
for (int i = 1; i <= n; i++)
tmp += sqrt((nx - x[i]) * (nx - x[i]) + (ny - y[i]) * (ny - y[i]));
return tmp;
}
inline int read()
{
int x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
inline void sa()
{
double t = 10000000;
while (t > 1e-14)
{
double nowx = ansx + (rand() * 2 - RAND_MAX) * t;
double nowy = ansy + (rand() * 2 - RAND_MAX) * t;
double tmp = calc(nowx, nowy) - calc(ansx, ansy);
if (tmp < 0)
ansx = nowx, ansy = nowy;
else if (exp(-tmp / t) * RAND_MAX > rand())
ansx = nowx, ansy = nowy;
t *= delta;
}
}
int main()
{
srand(time(NULL));
int T = read();
while (T--)
{
ansx = ansy = 0;
n = read();
for (int i = 1; i <= n; i++)
x[i] = read(), y[i] = read();
for (int i = 1; i <= 100; i++)
sa();
printf("%.0lf\n", calc(ansx, ansy));
if(T)
printf("\n");
}
return 0;
}
|