1 /* 3285 */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8  9 #define MAXN 5510 11 typedef struct {12     int x, y;13 } Point_t;14 15 Point_t points[MAXN];16 Point_t stack[MAXN];17 int top;18 19 void output(int);20 21 double dist(Point_t a, Point_t b) {22     return sqrt(1.0*(a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));23 }24 25 int dist2(Point_t a, Point_t b) {26     return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);27 }28 29 int cross(Point_t a, Point_t b, Point_t c) {30     return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);31 }32 33 bool comp(Point_t a, Point_t b) {34     int m = cross(points[0], a, b);35     return m>0 || (m==0 && dist2(points[0], a)<dist2(points[0], b));36 }37 38 void Graham(int n) {39     Point_t p;40     int i, j, k;41     42     p = points[0];43     k = 0;44     for (i=1; i<n; ++i) {45         if (points[i].x<p.x || (points[i].x==p.x && points[i].y<p.y)) {46             p = points[i];47             k = i;48         }49     }50     points[k] = points[0];51     points[0] = p;52     53     sort(points+1, points+n, comp);54     55     stack[0] = points[0];56     stack[1] = points[1];57     top = 1;58     59     for (i=2; i<n; ++i) {60         while(top && cross(stack[top-1], stack[top], points[i])<=0)61             --top;62         stack[++top] = points[i];63     }64 }65 66 int main() {67     int t, case_n;68     int n;69     int i, j, k;70     Point_t p;71     72 #ifndef ONLINE_JUDGE73     freopen("data.in", "r", stdin);74 #endif75 76     scanf("%d", &t);77     while (t--) {78         scanf("%d %d", &case_n, &n);79         for (i=0; i<n; ++i)80             scanf("%d %d", &points[i].x, &points[i].y);81         Graham(n);82         printf("%d %d\n", case_n, top+1);83         p = stack[0];84         k = 0;85         for (i=1; i<=top; ++i) {86             if (stack[i].y>p.y || (stack[i].y==p.y && stack[i].x<p.x)) {87                 p = stack[i];88                 k = i;89             }90         }91         for (i=k; i>=0; --i)92             printf("%d %d\n", stack[i].x, stack[i].y);93         for (i=top; i>k; --i)94             printf("%d %d\n", stack[i].x, stack[i].y);95     }96 97     return 0;98 }