刚开始学随机算法，凸包+模拟退火。

1 /* 2440 */  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
          
            8 using namespace std; 9 10 #define MAXN 105 11 12 typedef struct { 13 int x, y; 14 } Point_t; 15 16 Point_t stack[MAXN]; 17 Point_t points[MAXN]; 18 int dir[8][2] = { 19 {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1}, 20 {-1, -1}, {-1, 1}, { 1, -1}, { 1, 1} 21 }; 22 const double eps = 1e-10; 23 const double next = 0.9; 24 int n, top; 25 int ans; 26 27 double Length(Point_t a, Point_t b) { 28 return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + 0.); 29 } 30 31 int Length2(Point_t a, Point_t b) { 32 return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); 33 } 34 35 int cross(Point_t a, Point_t b, Point_t c) { 36 return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y); 37 } 38 39 bool comp(Point_t a, Point_t b) { 40 int m = cross(points[0], a, b); 41 return m>0 || (m==0 && Length2(points[0], a)
           
            1 && cross(stack[top-1], stack[top], points[i])<=0) 66 --top; 67 stack[++top] = points[i]; 68 } 69 } 70 71 double cal(double xx, double yy) { 72 double ret = 0; 73 double x, y; 74 75 for (int i=0; i<=top; ++i) { 76 x = xx - stack[i].x; 77 y = yy - stack[i].y; 78 ret += sqrt(x*x + y*y); 79 } 80 81 return ret; 82 } 83 84 void SA() { 85 double step = 10000.; 86 double dis, tmp; 87 double x, y; 88 double xx, yy; 89 int i; 90 91 x = stack[0].x; 92 y = stack[0].y; 93 dis = cal(x, y); 94 while (step > eps) { 95 for (i=0; i<8; ++i) { 96 xx = x + step * dir[i][0]; 97 yy = y + step * dir[i][1]; 98 tmp = cal(xx, yy); 99 if (tmp < dis) {100 dis = tmp;101 x = xx;102 y = yy;103 }104 }105 step *= next;106 }107 108 ans = (dis+0.5);109 }110 111 int main() {112 int t;113 int i, j, k;114 115 #ifndef ONLINE_JUDGE116 freopen("data.in", "r", stdin);117 //freopen("data.out", "w", stdout);118 #endif119 120 scanf("%d", &t);121 while (t--) {122 scanf("%d", &n);123 for (i=0; i