HDU 3340 Rain in ACStar

pid=3340" target="_blank" style="">题目链接

题意：给定几个多边形（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;

}