覆蓋的面積

Time Limit: 10000/5000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Problem Description 給定平面上若干矩形,求出被這些矩形覆蓋過至少兩次的區域的面積.



Input 輸入數據的第一行是一個正整數T(1<=T<=100),代表測試數據的數量.每個測試數據的第一行是一個正整數N(1<=N<=1000),代表矩形的數量,然后是N行數據,每一行包含四個浮點數,代表平面上的一個矩形的左上角坐標和右下角坐標,矩形的上下邊和X軸平行,左右邊和Y軸平行.坐標的范圍從0到100000.

注意:本題的輸入數據較多,推薦使用scanf讀入數據.

Output 對于每組測試數據,請計算出被這些矩形覆蓋過至少兩次的區域的面積.結果保留兩位小數.

Sample Input 2 5 1 1 4 2 1 3 3 7 2 1.5 5 4.5 3.5 1.25 7.5 4 6 3 10 7 3 0 0 1 1 1 0 2 1 2 0 3 1
Sample Output 7.63 0.00 解題思路：這道題目我完全沒有思路，后面只能搜別人的解題報告了。。可惜還是沒有弄懂。。 線段樹的節點包含以下幾部分
左右邊界l,r此區間被改的次數count,被覆蓋一次的長度len，覆蓋多次的
長度nlen
每條平行與Y軸直線包括這條線段，x坐標，上下y坐標，還有標記它是前線段
還是后線段的flag;
首先將矩形上所有的Y坐標完全映射到Y坐標上離散化，剔除重復值
建立線段樹
存儲平行于Y軸的直線
然后檢查每條線段，算出面積
面積累加
len（）函數是更新一次覆蓋的長度
nlen（）函數是更新覆蓋多次的長度

我們假設len[2]為當前線段被覆蓋了兩次的長度，len[1]為當前線段被覆蓋了一次的長度，而len[0]就是這條線段的長度，并且滿足len[2]+len[1]=len[0]。

? ? ? ? 首先，如果當前這條線段已經被覆蓋了兩次了，那么這條線段的len[2]就應該等于len[0]，而len[1]就應該等于0。

? ? ? ? 其次，如果當前這條線段被覆蓋了一次，那么這條線段的len[2]就應該是，左右子線段的len[2]的和加上左右子線段的len[1]，當然，前提是當前線段不能是線段樹中的葉子結點，否則它就沒有左右子線段不是嗎？這時候，當前線段的len[2]就應該等于0。而len[1]就等于len[0]，最后要注意當前線段的len[1]要減去len[2]，以滿足len[1]+len[2]=len[0]。

? ? ? ? 最后，如果這條線段沒有被覆蓋過，并且當前線段不是線段樹里的葉子結點，那么它的len[1]和len[2]都應該從它的左右子線段的len[1]和len[2]得到，如果是葉子結點，那么len[1]和len[2]都等于0。

AC: #include<stdio.h> #include<algorithm> using namespace std; #define MAX 1100 typedef struct {double x,y1,y2;__int64 flag; }LINE; typedef struct {__int64 l,r,count;double len,nlen;}NODE; LINE line[2*MAX]; NODE T[10*MAX]; double Y[2*MAX],tem[2*MAX]; bool comp(LINE a,LINE b) {if(a.x<b.x)return true;if(a.x==b.x&&a.flag<b.flag)return true;return false; } void Build__tree(__int64 i,__int64 l,__int64 r) {T[i].l=l;T[i].r=r;T[i].len=T[i].nlen=0;T[i].count=0;if(l+1==r)return;__int64 mid;mid=(l+r)/2;Build__tree(2*i,l,mid);Build__tree(2*i+1,mid,r); } void Len(__int64 root) {if(T[root].count>0)T[root].len=Y[T[root].r]-Y[T[root].l];elseT[root].len=T[2*root].len+T[2*root+1].len;} void nLen(__int64 root) {if(T[root].count>1)T[root].nlen=Y[T[root].r]-Y[T[root].l];else if(T[root].count==1)T[root].nlen=T[root*2].len+T[root*2+1].len;elseT[root].nlen=T[root*2].nlen+T[root*2+1].nlen;} void Update(__int64 root,LINE L) {if(L.y1==Y[T[root].l]&&L.y2==Y[T[root].r]){T[root].count+=L.flag;Len(root);nLen(root);return ;}LINE L1,L2;if(L.y1>=Y[T[2*root+1].l])Update(2*root+1,L);else if(L.y2<=Y[T[2*root].r])Update(2*root,L);else{L1=L2=L;L1.y2=Y[T[2*root].r];L2.y1=Y[T[2*root+1].l];Update(2*root,L1);Update(2*root+1,L2);}Len(root);nLen(root); } int main() {__int64 t,N,i,k;scanf("%I64d",&t);while(t--){double x1,x2,y1,y2;__int64 j;scanf("%I64d",&N);for(i=1,k=1;i<=N;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);line[k].x=x1;line[k].y1=y1;line[k].y2=y2;line[k].flag=1;tem[k++]=y1;line[k].x=x2;line[k].y1=y1;line[k].y2=y2;line[k].flag=-1;tem[k++]=y2;}sort(line+1,line+2*N+1,comp);sort(tem+1,tem+2*N+1);j=1;Y[1]=tem[1];for(i=2;i<=2*N;i++){if(tem[i]==tem[i-1])continue;Y[++j]=tem[i];}Build__tree(1,1,j);double area=0;for(i=1;i<=2*N;i++){if(i>1)area=area+(line[i].x-line[i-1].x)*T[1].nlen;Update(1,line[i]);}printf("%.2lf\n",area);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1255（线段树+离散化）的全部內容，希望文章能夠幫你解決所遇到的問題。

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