poj1389 Area of Simple Polygons

#include #include #include #include #include #include #include #include #include using namespace std; inline char read() { static const int IN_LEN = 1024 * 1024; static char buf[IN_LEN], *s, *t; if (s == t) { t = (s = buf) + fread(buf, 1, IN_LEN, stdin); if (s == t) return -1; } return *s++; } template inline bool R(T &x) { static char c; static bool iosig; for (c = read(), iosig = false; !isdigit(c); c = read()) { if (c == -1) return false; if (c == '-') iosig = true; } for (x = 0; isdigit(c); c = read()) x = (x << 3) + (x << 1) + (c ^ '0'); if (iosig) x = -x; return true; } const int OUT_LEN = 1024 * 1024; char obuf[OUT_LEN], *oh = obuf; inline void writechar(char c) { if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf; *oh++ = c; } template inline void W(T x) { static int buf[30], cnt; if (!x) writechar(48); else { if (x < 0) writechar('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) writechar(buf[cnt--]); } } inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); } const int MAXN = 50000 + 10; struct Tree { int cover; int sum; } tree[MAXN << 2]; struct node { int x, y1, y2, k; bool operator < (const node &a) const { return x < a.x; } } a[MAXN]; inline void update(int k, int l, int r) { if (tree[k].cover) tree[k].sum = r - l; else if (r == l + 1) tree[k].sum = 0; else tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum; } inline void modify(int k, int l, int r, int ql, int qr, int cnt) { // cout << l << " " << r << " " << ql << " " << qr << endl; if (ql <= l && r <= qr) tree[k].cover += cnt; /*不能在这一步直接return,一定要跑完update，否则会WA的很惨*/ else { int mid = l + r >> 1; if (ql < mid) modify(k << 1, l, mid, ql, qr, cnt); if (qr > mid) modify(k << 1 | 1, mid, r, ql, qr, cnt); } update(k, l, r); } int main() { // freopen("in.in", "r", stdin); int x1, x2, y1, y2, tot, ans; while (true) { tot = 0, ans = 0; R(x1), R(y1), R(x2), R(y2); if (x1 + y1 + x2 + y2 == -4) break; a[++tot].x = x1, a[tot].y1 = y1, a[tot].y2 = y2, a[tot].k = 1; a[++tot].x = x2, a[tot].y1 = y1, a[tot].y2 = y2, a[tot].k = -1; while (true) { R(x1), R(y1), R(x2), R(y2); if (x1 + y1 + x2 + y2 == -4) break; a[++tot].x = x1, a[tot].y1 = y1, a[tot].y2 = y2, a[tot].k = 1; a[++tot].x = x2, a[tot].y1 = y1, a[tot].y2 = y2, a[tot].k = -1; } sort(a + 1, a + tot + 1); // for (int i = 1; i <= tot; ++i) // cout << a[i].x << " " << a[i].y1 << " " << a[i].y2 << '\n'; modify(1, 0, MAXN, a[1].y1, a[1].y2, a[1].k); for (int i = 2; i <= tot; ++i) { ans += tree[1].sum * (a[i].x - a[i - 1].x); modify(1, 0, MAXN, a[i].y1, a[i].y2, a[i].k); } W(ans), writechar('\n'); } flush(); return 0; }