发现一个很神奇的事情。
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 50010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
const dd delta=0.996;
const dd t0=3000;
const dd eps=1e-15;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
struct point{
dd x,y;
point(){}
point(dd x,dd y) : x(x),y(y) {}
};
point p[N];
int T,n;
dd sumx,sumy,ans,ansx,ansy;
inline dd dis(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline dd all_dis(dd x,dd y){
dd res=0;
for(int i=1;i<=n;i++) res+=dis(point(x,y),p[i]);
return res;
}
inline void simulate(){
dd x=ansx,y=ansy;
dd t=t0;
while(t>eps){
dd dx=x+((rand()<<1)-RAND_MAX)*t;
dd dy=y+((rand()<<1)-RAND_MAX)*t;
dd now=all_dis(dx,dy);dd del=now-ans;
if(del<0){
x=dx;y=dy;ans=now;ansx=dx;ansy=dy;
}
else if(exp(-del/t)*RAND_MAX>rand()) x=dx,y=dy;
t*=delta;
}
}
inline void work(){
ansx=sumx/n;ansy=sumy/n;
for(int i=1;i<=5;i++) simulate();
}
int main(){
srand(time(0));
read(T);
while(T--){
ans=INF;sumx=0;sumy=0;
read(n);
for(int i=1;i<=n;i++){
read(p[i].x);read(p[i].y);
sumx+=p[i].x;sumy+=p[i].y;
}
work();
// printf("%lf\n",ans);
printf("%.0lf\n",round(ans));
if(T) printf("\n");
}
return 0;
}
在那个结构体里,如果把所有的 dd
改成 int
那么每一次模拟退火的答案都不一样,请问有这么大偏差的原因是什么?