A Star not a Tree?
#include <bits/stdc++.h>
using namespace std;
int t, n;
struct node
{double x, y;
}cur, np;
node a[110];
double ans, dt;
double rand(double l, double r)
{return (double)rand()/RAND_MAX*(r-l)+l;
}
double calc(node p)
{double sum=0;for(int i=1; i<=n; ++i){sum+=sqrt((p.x-a[i].x)*(p.x-a[i].x)+(p.y-a[i].y)*(p.y-a[i].y));}ans=min(ans, sum);return sum;
}
void simulate_anneal()
{cur.x=rand(0, 10000);cur.y=rand(0, 10000);for(double t=1e4; t>=1e-4; t*=0.99){np.x=rand(cur.x-t, cur.x+t);np.y=rand(cur.y-t, cur.y+t);dt=calc(np)-calc(cur);if(exp(-dt/t)>rand(0, 1)){cur=np;}}
}
int main()
{srand(time(0));scanf("%d", &t);while(t--){ans=1e9;scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%lf %lf", &a[i].x, &a[i].y);}for(int i=1; i<=100; ++i){simulate_anneal();}printf("%.0lf\n", ans);if(t!=0){printf("\n");}}return 0;
}
P1166 打保龄球
