题目链接
题意:给定几个多边形(3-5 边形),然后中间有一些询问。询问一个区间的总面积
思路:多边形切割为梯形,梯形的面积为上底 d1 + 下底 d2 乘上 高度 / 2。两个梯形面积累加的话,能够等价为上底下底累加,所以就能够用线段树搞了,然后给定的多边形点是按顺序的,能够利用容斥去方便把一个询问拆分成几个询问
代码:
- #include < cstdio > #include < cstring > #include < algorithm > #include < cmath > 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;
- }
来源: http://www.bubuko.com/infodetail-2148897.html