居然1Y了，以前写的模拟退火很靠谱啊。
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <cmath> 5 #include <ctime> 6 #include <cstdlib> 7 #include <iostream> 8 using namespace std; 9 struct point 10 { 11 double x,y; 12 }p[201]; 13 int n; 14 int a[4] = {0,0,-1,1}; 15 int b[4] = {1,-1,0,0}; 16 double dis(double x1,double y1,double x2,double y2) 17 { 18 return sqrt((x1-x2)*(x1-x2)+(y2-y1)*(y2-y1)); 19 } 20 double fun(double x,double y) 21 { 22 double ans = 0; 23 int i; 24 for(i = 0;i < n;i ++) 25 { 26 ans += dis(p[i].x,p[i].y,x,y); 27 } 28 return ans; 29 } 30 int main() 31 { 32 int T,i,key,num,j,k; 33 double tx,ty,ans,d,x,y; 34 srand(time(NULL)); 35 scanf("%d",&n); 36 for(i = 0;i < n;i ++) 37 { 38 scanf("%lf%lf",&p[i].x,&p[i].y); 39 } 40 key = 5; 41 ans = 100000000; 42 num = 200; 43 x = p[0].x; 44 y = p[0].y; 45 T = 40; 46 while(T--) 47 { 48 for(i = 1;i <= num;i ++) 49 { 50 for(j = 0;j < 4;j ++) 51 { 52 k = rand()%key; 53 tx = x + k*a[j]*T; 54 ty = y + k*b[j]*T; 55 if(tx >= 0&&tx <= 10000&&ty >= 0&&ty <= 10000) 56 { 57 d = fun(tx,ty); 58 if(ans > d) 59 { 60 ans = d; 61 x = tx; 62 y = ty; 63 } 64 } 65 } 66 } 67 } 68 printf("%.f ",ans); 69 return 0; 70 }