题意

给出n个矩形，求面积并。

思路

使用扫描线，我这里离散化y轴，按照x坐标从左往右扫过去。离散化后的y轴可以用线段树维护整个y上面的线段总长度，当碰到扫描线的时候，就可以统计面积。这里要注意线段树上结点维护的是线段的信息，而不是点的信息。

参考资料

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int N = 1e5 + 10;

#define lson l, m, rt<<1

#define rson m + 1, r, rt<<1|1

struct Node {

	int st;

	double l, r, id;

	bool operator < (const Node &rhs) const {

		return id < rhs.id;

	}

} p[N];

double y[N], tree[N<<2];

int cnt[N<<2];

void PushUp(int l, int r, int rt) {

	if(cnt[rt] > 0) tree[rt] = y[r+1] - y[l]; // r + 1是因为线段树上结点是线段,映射成点就要+1

	else if(l == r) tree[rt] = 0; // 当这个线段没有cnt的时候就代表消失了

	else tree[rt] = tree[rt<<1] + tree[rt<<1|1];

}

void Update(int L, int R, int w, int l, int r, int rt) {

	if(L <= l && r <= R) {

		cnt[rt] += w;

		PushUp(l, r, rt);

		return ;

	}

	int m = (l + r) >> 1;

	if(L <= m) Update(L, R, w, lson);

	if(m < R) Update(L, R, w, rson);

	PushUp(l, r, rt);

}

int main() {

	int cas = 1, n;

	while(scanf("%d", &n), n) {

		int cnt = 0, m = 0;

		for(int i = 1; i <= n; i++) {

			double x1, x2, y1, y2;

			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

			y[++cnt] = y1, y[++cnt] = y2;

			p[++m] = (Node) { 1, y1, y2, x1 };

			p[++m] = (Node) { -1, y1, y2, x2 };

		}

		sort(y + 1, y + 1 + cnt);

		sort(p + 1, p + 1 + m);

		cnt = unique(y + 1, y + 1 + cnt) - y - 1;

		double ans = 0;

		for(int i = 1; i <= m; i++) {

			ans += tree[1] * (p[i].id - p[i-1].id);

			int L = lower_bound(y + 1, y + 1 + cnt, p[i].l) - y;

			int R = lower_bound(y + 1, y + 1 + cnt, p[i].r) - y - 1;

					// R - 1是因为线段树上的结点是线段

			Update(L, R, p[i].st, 1, cnt, 1);

			printf("%d : %d - %d , %.2f\n", i, L, R, tree[1]);

		}

		printf("Test case #%d\n", cas++);

		printf("Total explored area: %.2f\n\n", ans);

	}

	return 0;

}

巴特西

HDU 1542：Atlantis（扫描线+线段树矩形面积并）***

题意

思路

最新文章

热门文章

巴特西

HDU 1542：Atlantis（扫描线+线段树 矩形面积并）***

题意

思路

最新文章

热门文章

HDU 1542：Atlantis（扫描线+线段树矩形面积并）***