有点惊险的一天。
早上11点去杭州的飞机，我和队友们本来计划9点从五山出发的，结果拖迟了十几分钟。幸运的是，地铁速度够快，压哨2分钟从取票处拿到机票了。
飞机飞了两个钟就到杭州，然后我们坐机场大巴到武林门，再转的士到酒店。自费的比赛，开支各种心疼。TAT
到了酒店，我们入住一间3人房，设备足够简陋，居然还要一人100块一个晚上，继续心疼。TAT
然后，查了一下地图，酒店是多么的偏僻。_(:з」∠)_本来以为是在浙工大附近住的，然后我们就可以自助去西湖游一下，最后看到这么偏僻的地方，出去市中心打的要50块，坐公交6点多就收车了，最后就只好决定在酒店呆3天算了。
晚餐没有自助餐，不过还是挺丰富的，除了一人一份菜，白饭任拿，饭还送到酒店房间来，勉强没那么多怨言了。
然后剩下几个钟，就一直卡一道LOJ的几何题1313，以为早上想到的思路应该没错了，结果敲出来还是各种WA。
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 6 using namespace std; 7 8 struct Point { 9 int x, y; 10 Point() {} 11 Point(int x, int y) : x(x), y(y) {} 12 } ; 13 Point operator + (Point a, Point b) { return Point(a.x + b.x, a.y + b.y);} 14 Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y);} 15 bool operator < (Point a, Point b) { return a.x < b.x || a.x == b.x < a.y < b.y;} 16 inline int crossDet(Point a, Point b) { return a.x * b.y - a.y * b.x;} 17 inline int crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);} 18 inline int dotDet(Point a, Point b) { return a.x * b.x + a.y * b.y;} 19 20 inline bool onSeg(Point p, Point a, Point b) { return crossDet(p, a, b) == 0 && dotDet(a - p, b - p) < 0;} 21 22 int ptInPoly(Point p, Point *poly, int sz) { 23 int wn = 0; 24 poly[sz] = poly[0]; 25 for (int i = 0; i < sz; i++) { 26 if (onSeg(p, poly[i], poly[i + 1])) return -1; 27 int k = crossDet(poly[i], poly[i + 1], p); 28 int d1 = poly[i].y - p.y; 29 int d2 = poly[i + 1].y - p.y; 30 if (k > 0 && d1 <= 0 && d2 > 0) wn++; 31 if (k < 0 && d2 <= 0 && d1 > 0) wn--; 32 } 33 if (wn != 0) return 1; 34 return 0; 35 } 36 37 int andrew(Point *pt, int n, Point *ch) { 38 int m = 0; 39 sort(pt, pt + n); 40 for (int i = 0; i < n; i++) { 41 while (m > 1 && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--; 42 ch[m++] = pt[i]; 43 } 44 int k = m; 45 for (int i = n - 2; i >= 0; i--) { 46 while (m > k && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--; 47 ch[m++] = pt[i]; 48 } 49 if (n > 1) m--; 50 return m; 51 } 52 53 const int N = 111; 54 55 int inPoly(Point *mines, int m, Point *poly, int p) { 56 int ret = 0; 57 for (int i = 0; i < m; i++) { 58 if (int t = ptInPoly(mines[i], poly, p)) { 59 if (t == -1) { 60 puts("shit!!!"); 61 while (1) ; 62 } 63 mines[ret++] = mines[i]; 64 } 65 } 66 return ret; 67 } 68 69 bool mat[N][N], res[N][N], cur[N][N]; 70 71 bool allOnLeft(Point a, Point b, Point *s, int m) { 72 for (int i = 0; i < m; i++) { 73 if (crossDet(a, b, s[i]) >= 0) return false; 74 } 75 return true; 76 } 77 78 int work(Point *holes, int h, Point *mines, int m) { 79 memset(mat, 0, sizeof(mat)); 80 memset(res, 0, sizeof(res)); 81 for (int i = 0; i < h; i++) { 82 for (int j = 0; j < h; j++) { 83 if (i == j) continue; 84 if (allOnLeft(holes[i], holes[j], mines, m)) mat[i][j] = res[i][j] = true; 85 } 86 } 87 // for (int i = 0; i < h; i++) { 88 // cout << "holes " << holes[i].x << ' ' << holes[i].y << endl; 89 // } 90 // for (int i = 0; i < m; i++) { 91 // cout << "mines " << mines[i].x << ' ' << mines[i].y << endl; 92 // } 93 // for (int i = 0; i < h; i++) { 94 // for (int j = 0; j < h; j++) { 95 // cout << mat[i][j]; 96 // } 97 // cout << endl; 98 // } 99 // cout << "check" << endl; 100 for (int t = 1; t <= h; t++) { 101 for (int i = 0; i < h; i++) { 102 if (res[i][i]) { 103 // cout << i << endl; 104 return t; 105 } 106 for (int j = 0; j < h; j++) { 107 cur[i][j] = res[i][j]; 108 } 109 } 110 memset(res, 0, sizeof(res)); 111 for (int i = 0; i < h; i++) { 112 for (int k = 0; k < h; k++) { 113 if (cur[i][k]) { 114 for (int j = 0; j < h; j++) { 115 res[i][j] = cur[i][k] && mat[k][j]; 116 } 117 } 118 } 119 } 120 } 121 puts("damn!"); 122 while (1) ; 123 return 0; 124 } 125 126 int main() { 127 freopen("in", "r", stdin); 128 int T, n, m, g, p; 129 Point holes[N], mines[N], poly[N]; 130 cin >> T; 131 for (int cas = 1; cas <= T; cas++) { 132 cin >> n >> m >> g >> p; 133 for (int i = 0; i < n; i++) cin >> holes[i].x >> holes[i].y; 134 for (int i = 0; i < m; i++) cin >> mines[i].x >> mines[i].y; 135 int t = andrew(holes, n, poly); 136 // cout << "Convex Hull" << endl; 137 int k = inPoly(mines, m, poly, t); 138 // cout << "inPoly" << endl; 139 int ans1 = (m - k) * g; 140 t = k ? work(holes, n, mines, k) : 0; 141 int ans2 = t * p; 142 // cout << ans1 << ' ' << ans2 << endl; 143 cout << "Case " << cas << ": " << ans1 + ans2 << endl; 144 } 145 return 0; 146 }
好不爽的一个晚上。。
明天热身，求后天可以爆状态。
——written by Lyon