郁闷啊郁闷，写了两个凸包的题目，都折戟在一两个NB数据上了。
tyvj上P1462的程序，赤果果的求凸包。自己写的Graham扫描法，极角顺序，从最下最右的点开始：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <stdio.h>#include <stdlib.h>#include <math.h>#ifndef M_PI#define M_PI 3.14159265358979323846#endiftypedef struct { double x, y, tg;} coord;// 算极角inline double calc_tg (const coord b, const coord n){ double ret = atan2(n.y-b.y, n.x-b.x); return ret >= 0 ? ret:ret+2*M_PI;}// 判断是否左转#define tleft(a,b,c) \ (((b).x-(a).x)*((c).y-(a).y)-((c).x-(a).x)*((b).y-(a).y) <= 0.0)// 快排之比较int comp (const void *pa, const void *pb){ const coord *a = (const coord*)pa, *b = (const coord*)pb; if (a->tg > b->tg) return 1; else if (a->tg != b->tg) return -1; else return a->x > b->x ? 1:-1;}int main (){ int n, i, stktail; coord *p, **stk, minc = {0.0, 1.0E22}; // 读入数据 scanf("%d", &n); p = malloc(n*sizeof(coord)); stk = malloc(n*sizeof(coord*)); for (i=0; i<n; i++) { scanf("%lf %lf", &(p[i].x), &(p[i].y)); if ((p[i].y < minc.y) || ((p[i].y == minc.y) && (p[i].x < minc.x))) minc = p[i]; } // 求凸包 for (i=0; i<n; i++) p[i].tg = calc_tg(minc, p[i]); qsort(p, n, sizeof(coord), comp); stk[0] = p; stk[1] = p+1; stk[2] = p+2; stktail = 2; for (i=3; i<n; i++) { while (stktail >= 1) { coord *base = stk[stktail-1], *last = stk[stktail]; if (tleft(*base, *last, p[i])) stktail--; else break; } stk[++stktail] = p+i; } while (stk[stktail]->tg == stk[stktail-1]->tg) stktail--; // 按要求的顺序输出 int st = 0; double minx = stk[0]->x; for (i=stktail; i>=0; i--) { if (stk[i]->x < minx) minx = stk[i]->x, st = i; else break; } i = st; do { printf("%.4lf %.4lf\n", stk[i]->x, stk[i]->y); if (--i < 0) i = stktail; } while (i != st); return 0;} |
运行结果：...
