題意：
? ? ? 給你n個矩形，然后問你這n個矩形所組成的畫面中被覆蓋至少兩次的面積有多大。
思路：
? ? ? 和1542差距并不是很大，大體上還是離散化+線段樹掃面線，不同的地方就是這個題目要求覆蓋至少兩次，那么假如l1:覆蓋一次的區間長度,l2：覆蓋至少兩次的區間長度， l3：整個區間的長度，并且滿足 l1 + l2 = l3,cnt為區間覆蓋次數，那么在更新pushup的時候
?(1)cnt >= 2 那么l2 = l3 ,l1 = 0
?(2)cnt == 1 那么l2 = 左邊l1 + 右邊l1 + 左邊l2 + 右邊l2,l1 = l3 - l2

?(3)cnt == 0 那么如果是葉子了l1 = l2 = 0,否則正常更新l1=l1左+l1右，l2=l2左+l2右.

#include<stdio.h> #include<string.h> #include<algorithm>#define lson l ,mid ,t << 1 #define rson mid ,r ,t << 1 | 1 #define N_node 10000 using namespace std;typedef struct {double l ,r ,h;int mk; }EDGE;EDGE edge[N_node]; double len1[N_node] ,len2[N_node]; int cnt[N_node]; double tmp[N_node] ,num[N_node];bool camp(EDGE a ,EDGE b) {return a.h < b.h; }void Pushup(int l ,int r ,int t) {if(cnt[t] >= 2){len2[t] = num[r] - num[l];len1[t] = 0;}else if(cnt[t] == 1){len2[t] = len2[t<<1] + len2[t<<1|1] + len1[t<<1] + len1[t<<1|1];len1[t] = num[r] - num[l] - len2[t];}else {if(l + 1 == r){len2[t] = len1[t] = 0;}else {len2[t] = len2[t<<1] + len2[t<<1|1];len1[t] = len1[t<<1] + len1[t<<1|1];}} }void Update(int l ,int r ,int t ,int a ,int b ,int c) {if(a == l && b == r){cnt[t] += c;Pushup(l ,r ,t);return;}int 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); }int search_2(int id ,double now) {int low = 1 ,up = id ,mid ,ans;while(low <= up){mid = (low + up) >> 1;if(now <= num[mid]){ans = mid;up = mid - 1;}else low = mid + 1;}return ans; }int main () {int t ,i ,id ,n;double x1 ,x2 ,y1 ,y2 ,sum;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(id = 0 ,i = 1 ;i <= n ;i ++){scanf("%lf %lf %lf %lf" ,&x1 ,&y1 ,&x2 ,&y2);edge[++id].l = x1;edge[id].r = x2 ,edge[id].h = y1 ,edge[id].mk = 1;tmp[id] = x1;edge[++id].l = x1;edge[id].r = x2 ,edge[id].h = y2 ,edge[id].mk = -1;tmp[id] = x2;}sort(tmp + 1 ,tmp + id + 1);sort(edge + 1 ,edge + id + 1 ,camp);for(id = 0 ,i = 1 ;i <= n * 2 ;i ++)if(i == 1 || tmp[i] != tmp[i-1])num[++id] = tmp[i];memset(cnt ,0 ,sizeof(cnt));memset(len1 ,0 ,sizeof(len1));memset(len2 ,0 ,sizeof(len2));edge[0].h = edge[1].h;for(sum = 0 ,i = 1 ;i <= n * 2 ;i ++){sum += len2[1] * (edge[i].h - edge[i-1].h);int l = search_2(id ,edge[i].l);int r = search_2(id ,edge[i].r);Update(1 ,id ,1 ,l ,r ,edge[i].mk);}printf("%.2lf\n" ,sum);}return 0; }

總結

以上是生活随笔為你收集整理的hdu1255 扫描线，矩形重叠面积（两次以上）的全部內容，希望文章能夠幫你解決所遇到的問題。

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