Overlapping Rectangles（线段树，矩形面积并）

Overlapping Rectangles（线段树，矩形面积并）

Although the problem looks simple at the first glance, it might take a while to figure out how to do it correctly. Note that the shape of the union can be very complicated, and the intersected areas can be overlapped by more than two rectangles.

Note:

(2) To make the problem easier, you do not have to worry about the sum of the areas exceeding the long integer precision. That is, you can assume that the total area does not result in integer overflow.

Input Format

Output Format

For each set of the rectangles configurations appeared in the input, calculate the total area of the union of the rectangles. Again, these rectangles might overlap each other, and the intersecting areas of these rectangles can only be counted once. Output a single star '*' to signify the end of outputs.

样例输入

2 0 0 2 2 1 1 3 3 3 0 0 1 1 2 2 3 3 4 4 5 5 0

样例输出

7 3 *

题目大概：

求给出所有矩形，取并集后的面积。

思路：

线段树矩形面积并问题，模板题

代码：

#include #include #include #include using namespace std;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1#define LL long longconst int maxn = 2222;LL cnt[maxn << 2];LL sum[maxn << 2];LL X[maxn];struct Seg { LL h,l,r; int s; Seg(){} Seg(LL a,LL b,LL c,LL d) : l(a) , r(b) , h(c) , s(d) {} bool operator < (const Seg &cmp) const { return h < cmp.h; }}ss[maxn];void PushUp(int rt,int l,int r) { if (cnt[rt]) sum[rt] = X[r+1] - X[l]; else if (l == r) sum[rt] = 0; else sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { cnt[rt] += c; PushUp(rt , l , r); return ; } int m = (l + r) >> 1; if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson); PushUp(rt , l , r);}int Bin(LL key,LL n,LL X[]) { int l = 0 , r = n - 1; while (l <= r) { int m = (l + r) >> 1; if (X[m] == key) return m; if (X[m] < key) l = m + 1; else r = m - 1; } return -1;}int main() { int n , cas = 1; while (~scanf("%d",&n) && n) { int m = 0; while (n --) { int a , b , c , d; scanf("%d%d%d%d",&a,&b,&c,&d); X[m] = a; ss[m++] = Seg(a , c , b , 1); X[m] = c; ss[m++] = Seg(a , c , d , -1); } sort(X , X + m); sort(ss , ss + m); int k = 1; for (int i = 1 ; i < m ; i ++) { if (X[i] != X[i-1]) X[k++] = X[i]; } memset(cnt , 0 , sizeof(cnt)); memset(sum , 0 , sizeof(sum)); int ret = 0; for (int i = 0 ; i < m - 1 ; i ++) { int l = Bin(ss[i].l , k , X); int r = Bin(ss[i].r , k , X) - 1; if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1); ret += sum[1] * (ss[i+1].h - ss[i].h); } printf("%d\n",ret); } printf("*"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。