如题,曾经将代码写为了:
else if(exp( - DE / T) > rand() % RAND_MAX)
然后 AC 了……
#include <bits/stdc++.h>
using namespace std;
double X, Y;
int n;
int x[1005], y[1005];
double dis(double x1, double y1, double x2, double y2){
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double calc(double a, double b){
double minn = 0x7fffffff;
for(int i = 1;i <= n;i ++ ){
minn = min(minn, dis(a, b, 1.0 * x[i], 1.0 * y[i]));
}
return minn;
}
double rrand(double l, double r){
if(l > r) swap(l, r);
return rand() * (r - l) / RAND_MAX + l;
}
const double delta = 0.997;
double p, q, ans;
double a, b;
void SA(){
double T = 100000;
while(T > 1e-12){
double new_x = rrand(max(0.0, p - T), min(X, p + T));
double new_y = rrand(max(0.0, q - T), min(Y, q + T));
double new_ans = calc(new_x, new_y);
double DE = ans - new_ans;
if(DE < 0){
ans = new_ans;
p = new_x;
q = new_y;
a = p;
b = q;
}
// else if(exp( - DE / T) * RAND_MAX> rand()){
// p = new_x;
// q = new_y;
// }
T *= delta;
}
}
int main(){
srand(rand());
int T;
scanf("%d", &T);
while(T -- ){
scanf("%lf %lf %d", &X, &Y, &n);
for(int i = 1;i <= n;i ++ ){
scanf("%d %d", &x[i], &y[i]);
}
a = rrand(0, X);
b = rrand(0, Y);
ans = calc(a, b);
// cout<<ans<<endl;
for(int i = 1;i <= 10;i ++ ) SA();
// while(clock() < 0.9 * CLOCK_PER_SEC) SA();
printf("The safest point is (%.1lf, %.1lf).\n", a, b);
}
return 0;
}