凸包模板题目。
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 55 10 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_JUDGE 73 freopen("data.in", "r", stdin); 74 #endif 75 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 ", 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 ", stack[i].x, stack[i].y); 93 for (i=top; i>k; --i) 94 printf("%d %d ", stack[i].x, stack[i].y); 95 } 96 97 return 0; 98 }