1 /* 2440 */  2 #include <iostream>  3 #include <cstdio>  4 #include <cstring>  5 #include <cstdlib>  6 #include <cmath>  7 #include <algorithm>  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)<Length2(points[0], b)); 42 } 43  44 void Graham() { 45     int i, j, k; 46     Point_t p; 47      48     p = points[0]; 49     k = 0; 50     for (i=1; i<n; ++i) { 51         if (points[i].x<p.x || (points[i].x==p.x && points[i].y<p.y)) { 52             k = i; 53             p = points[i]; 54         } 55     } 56     points[k] = points[0]; 57     points[0] = p; 58      59     sort(points+1, points+n, comp); 60     stack[0] = points[0]; 61     stack[1] = points[1]; 62     top = 1; 63      64     for (i=2; i<n; ++i) { 65         while (top>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<n; ++i)124             scanf("%d %d", &points[i].x, &points[i].y);125         Graham();126         SA();127         printf("%d\n", ans);128         if (t)129             printf("\n");130     }131     132     return 0;133 }