題意：
? ? ? ?給你n個矩形，每個矩形上都有一個矩形的空洞，所有的矩形都是平行于x,y軸的，最后問所有矩形的覆蓋面積是多少。


思路：

? ? ? 是典型的矩形覆蓋問題，只不過每個矩形上多了一個矩形洞，我的做法是吧當前的矩形分成四個小的矩形，然后用線段樹的掃描線掃一遍就ok了，記得要用INT64 ,自己沒注意這個問題wa了一次。

#include<stdio.h> #include<string.h> #include<algorithm>#define N 300000 #define lson l ,mid ,t << 1 #define rson mid ,r ,t << 1 | 1 using namespace std;typedef struct {__int64 l ,r ,h ,mk; }EDGE;__int64 len[N] ,cnt[N]; EDGE edge[N*2];bool camp(EDGE a ,EDGE b) {return a.h < b.h || a.h == b.h && a.mk > b.mk; }void Pushup(__int64 l ,__int64 r ,__int64 t) {if(cnt[t]) len[t] = r - l;else if(l + 1 == r) len[t] = 0;else len[t] = len[t<<1] + len[t<<1|1]; }void Update(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b ,__int64 c) {//printf("%d %d %d\n" ,l ,r ,t); if(l == a && r == b){cnt[t] += c;Pushup(l ,r ,t);return;}__int64 mid = (l + r) >> 1;if(b <= mid) Update(lson ,a ,b ,c);else if(a >= mid) Update(rson ,a ,b ,c);else {Update(lson ,a ,mid ,c);Update(rson ,mid ,b ,c);}Pushup(l ,r ,t); }__int64 abss(__int64 x) {return x < 0 ? -x : x; }int main () {__int64 i ,j ,n ,x1 ,x2 ,x3 ,x4 ,y1 ,y2 ,y3 ,y4 ,id;__int64 xx1 ,xx2 ,yy1 ,yy2;while(~scanf("%I64d" ,&n) && n){for(id = 0 ,i = 1 ;i <= n ;i ++){scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d" ,&x1 ,&y1 ,&x2 ,&y2 ,&x3 ,&y3 ,&x4 ,&y4);x1 ++ ,y1 ++ ,x2 ++ ,y2 ++ ,x3 ++ ,y3 ++ ,x4 ++ ,y4 ++;// x1 y2 x2 y4 xx1 = x1 ,xx2 = x2 ,yy1 = y2 ,yy2 = y4;if(abss(xx1 - xx2) && abss(yy1 - yy2)){edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;}// x1 y3 x2 y1 xx1 = x1 ,xx2 = x2 ,yy1 = y3 ,yy2 = y1;if(abss(xx1 - xx2) && abss(yy1 - yy2)){edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;}// x1 y4 x3 y3 xx1 = x1 ,xx2 = x3 ,yy1 = y4 ,yy2 = y3;if(abss(xx1 - xx2) && abss(yy1 - yy2)){edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;}// x4 y4 x2 y3 xx1 = x4 ,xx2 = x2 ,yy1 = y4 ,yy2 = y3;if(abss(xx1 - xx2) && abss(yy1 - yy2)){edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy1 ,edge[id].mk = 1;edge[++id].l = xx1;edge[id].r = xx2 ,edge[id].h = yy2 ,edge[id].mk = -1;} }sort(edge + 1 ,edge + id + 1 ,camp);__int64 Ans = 0;memset(len ,0 ,sizeof(len));memset(cnt ,0 ,sizeof(cnt));edge[0].h = edge[1].h;for(i = 1 ;i <= id ;i ++){Ans += len[1] * (edge[i].h - edge[i-1].h);Update(1 ,50001,1 ,edge[i].l ,edge[i].r ,edge[i].mk);}printf("%I64d\n" ,Ans);}return 0; }

? ? ?

總結

以上是生活随笔為你收集整理的hdu 3265 线段树扫描线（拆分矩形）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。