1 /* 1348 */ 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 100511 12 typedef struct Point_t {13     double x, y;14     Point_t() {}15     Point_t(double xx, double yy) {16         x = xx; y = yy;17     }18 } Point_t;19 20 Point_t stack[MAXN];21 Point_t points[MAXN];22 const double PI = acos(-1.0);23 int n;24 25 double Length(Point_t a, Point_t b) {26     return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));27 }28 29 double cross(Point_t p0, Point_t p1, Point_t p2) {30     return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);31 }32 33 bool comp(Point_t a, Point_t b) {34     double k = cross(points[0], a, b);35     return !(k<0 || (k==0 && Length(points[0], a)>Length(points[0], b)));36 }37 38 double Graham() {39     double ret = 0;40     int i, j, k;41     int top;42     Point_t p0;43     44     p0 = points[0];45     k = 0;46     for (i=1; i<n; ++i) {47         if (points[i].x<p0.x || (points[i].x==p0.x && points[i].y<p0.y)) {48             p0 = points[i];49             k = i;50         }51     }52     53     points[k] = points[0];54     points[0] = p0;55     sort(points+1, points+n, comp);56     57     stack[0] = points[0];58     stack[1] = points[1];59     stack[2] = points[2];60     top = 2;61     for (i=3; i<n; ++i) {62         while (cross(stack[top-1], stack[top], points[i])<=0 && top>1)63             --top;64         stack[++top] = points[i];65     }66     stack[++top] = p0;67     for (i=1; i<=top; ++i)68         ret += Length(stack[i-1], stack[i]);69     70     return ret;71 }72 73 int main() {74     int t;75     int i, j, k, tmp;76     double l, ans;77     78     #ifndef ONLINE_JUDGE79         freopen("data.in", "r", stdin);80     #endif81     82     scanf("%d", &t);83     while (t--) {84         scanf("%d %lf", &n, &l);85         for (i=0; i<n; ++i)86             scanf("%lf %lf", &points[i].x, &points[i].y);87         ans = Graham();88         ans += PI * (l+l);89         printf("%.0lf\n", ans);90         if (t)91             printf("\n");92     }93     94     return 0;95 }