HDU 3340 Rain in ACStar
题意：给定几个多边形（3-5边形），然后中间有一些询问。询问一个区间的总面积
思路：多边形切割为梯形，梯形的面积为上底d1 + 下底d2 乘上 高度 / 2。两个梯形面积累加的话，能够等价为上底下底累加，所以就能够用线段树搞了，然后给定的多边形点是按顺序的，能够利用容斥去方便把一个询问拆分成几个询问
代码：
#include#include #include #include using namespace std;const int N = 133333;int t, n;struct Point { int x, y, id; Point() {} Point(int x, int y) { this->x = x; this->y = y; this->id = id; } void read() { scanf("%d%d", &x, &y); }} p[6];bool cmpp(Point a, Point b) { return a.x < b.x;}struct OP { int tp, l, r; double a, b; OP() {} OP(int l, int r, int tp, double a = 0.0, double b = 0.0) { this->l = l; this->r = r; this->tp = tp; this->a = a; this->b = b; }} op[N];int hash[N * 2], hn, opn;int find(int x) { return lower_bound(hash, hash + hn, x) - hash;}void build_p(int m) { p[m++] = p[0]; for (int i = 0; i < m - 1; i++) { if (p[i].x < p[i + 1].x) op[opn++] = OP(p[i].x, p[i + 1].x, 1, -p[i].y, -p[i + 1].y); else op[opn++] = OP(p[i + 1].x, p[i].x, 1, p[i + 1].y, p[i].y); }}#define lson(x) ((x<<1)+1)#define rson(x) ((x<<1)+2)struct Node { int l, r; double d1, d2, s; void gao(double a, double b) { d1 += a; d2 += b; s += (a + b) * (hash[r + 1] - hash[l]) / 2; }} node[N * 8];void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; node[x].d1 = node[x].d2 = node[x].s = 0; if (l == r) return; int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x));}double cal(double h1, double h2, double d1, double d2) { return (d2 * h1 + d1 * h2) / (h1 + h2);}void pushdown(int x) { double h1 = hash[node[lson(x)].r + 1] - hash[node[lson(x)].l]; double h2 = hash[node[rson(x)].r + 1] - hash[node[rson(x)].l]; double d = cal(h1, h2, node[x].d1, node[x].d2); node[lson(x)].gao(node[x].d1, d); node[rson(x)].gao(d, node[x].d2); node[x].d1 = node[x].d2 = 0;}void pushup(int x) { node[x].s = node[lson(x)].s + node[rson(x)].s;}void add(int l, int r, double a, double b, int x = 0) { if (node[x].l >= l && node[x].r <= r) { double d1 = cal(hash[node[x].l] - hash[l], hash[r + 1] - hash[node[x].l], a, b); double d2 = cal(hash[node[x].r + 1] - hash[l], hash[r + 1] - hash[node[x].r + 1], a, b); node[x].gao(d1, d2); return; } int mid = (node[x].l + node[x].r) / 2; pushdown(x); if (l <= mid) add(l, r, a, b, lson(x)); if (r > mid) add(l, r, a, b, rson(x)); pushup(x);}double query(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) return node[x].s; int mid = (node[x].l + node[x].r) / 2; double ans = 0; pushdown(x); if (l <= mid) ans += query(l, r, lson(x)); if (r > mid) ans += query(l, r, rson(x)); pushup(x); return ans;}int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); char ss[15]; int l, r, m; hn = opn = 0; while (n--) { scanf("%s", ss); if (ss[0] == 'Q') { scanf("%d%d", &l, &r); hash[hn++] = l; hash[hn++] = r; op[opn++] = OP(l, r, 0); } else { scanf("%d", &m); for (int i = 0; i < m; i++) { p[i].read(); hash[hn++] = p[i].x; } build_p(m); } } int tmp = 1; sort(hash, hash + hn); for (int i = 1; i < hn; i++) if (hash[i] != hash[i - 1]) hash[tmp++] = hash[i]; hn = tmp; build(0, hn - 2); for (int i = 0; i < opn; i++) { if (op[i].tp) add(find(op[i].l), find(op[i].r) - 1, op[i].a, op[i].b); else printf("%.3lf\n", query(find(op[i].l), find(op[i].r) - 1)); } } return 0;}