掃描線求矩形重疊面積：http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?http://www.tuicool.com/articles/6Zf6J3

這題參考：http://www.cppblog.com/menjitianya/archive/2011/03/30/143043.html

解題思路：線段樹+離散化

首先我們將每個矩形的縱向邊投影到Y(jié)軸上，這樣就可以把矩形的縱向邊看成一個閉區(qū)間，用線段樹來維護這些矩形邊的并。現(xiàn)在求的是矩形的面積并，于是可以枚舉矩形的x坐標(biāo)，然后檢測當(dāng)前相鄰x坐標(biāo)上y方向的合法長度，兩者相乘就是其中一塊面積，枚舉完畢后就求得了所有矩形的面積并。? 我的線段樹結(jié)點描述保存了以下信息：區(qū)間的左右端點、結(jié)點所在數(shù)組編號（因為采用靜態(tài)結(jié)點可以大大節(jié)省申請空間的時間）、該結(jié)點被豎直線段完全覆蓋的次數(shù)Cover和當(dāng)前結(jié)點覆蓋一次的y方向長度yOnce和當(dāng)前結(jié)點覆蓋多次的y方向長度yMore。
? ? 其實和矩形面積并的唯一差別就是在計算Cover后的Update函數(shù)，更新yOnce和yMore的值，分情況討論：
1.?當(dāng)nCover>1時，yOnce?=?0;?yMore?=?區(qū)間實際長度;
2.?當(dāng)nCover=1時，yMore?=?兩棵子樹的yOnce+yMore;?
? ? ? ? ? ? ? ? ?yOnce?=?區(qū)間實際長度?-?yMore;
3.?當(dāng)nCover=0時，如果是葉子結(jié)點?yOnce?=?0;?yMore?=?0;
? ? ? ? ? ? ? ? ?否則?
? ? ? ? ? ? ? ? ?yOnce?=?兩棵子樹的yOnce和;
? ? ? ? ? ? ? ? ?yMore?=?兩棵子樹的yMore和;

這題還是先要把掃描法看懂了，剩下的就好辦了。

AC:

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std;const int maxn = 2200; const double eps = 1e-6; double edge[maxn],tmp[maxn]; int tmpsize,size;struct Segment {int p,l,r;int nCover;double yOne,yMore;void Update(){if(nCover > 1){yOne = 0;yMore = edge[r] - edge[l];}else if(nCover == 1){yMore = tree[p<<1].yMore + tree[p<<1].yOne + tree[p<<1|1].yMore + tree[p<<1|1].yOne;yOne = edge[r] - edge[l] - yMore;}else{if(l + 1 == r) //葉子節(jié)點，無法拓展{yOne = yMore = 0;}else{yOne = tree[p<<1].yOne + tree[p<<1|1].yOne;yMore = tree[p<<1].yMore + tree[p<<1|1].yMore;}}} }tree[maxn<<2];struct Line {double x,y1,y2;int val;Line(){ }Line(double _x,double _y1,double _y2,double _val){x = _x;y1 = _y1;y2 = _y2;val = _val;} }; vector<Line> vec;bool cmp(Line a, Line b) {return a.x < b.x; }void DiscretData() {sort(tmp,tmp+tmpsize);size = 0;edge[++size] = tmp[0];for(int i = 1; i < tmpsize; i++)if(fabs(tmp[i] - tmp[i-1]) > eps)edge[++size] = tmp[i]; }void build(int o,int l,int r) {tree[o].l = l, tree[o].r = r;tree[o].nCover = tree[o].yMore = tree[o].yOne = 0;tree[o].p = o; if(l+1 == r || l == r) return;int mid = (l + r) >> 1;build(o<<1,l,mid);build(o<<1|1,mid,r); //這里不能是mid+1，因為算的是線段長度，如果是mid+1，會變成1-2和3-4的區(qū)間，中間2-3這一段就無法計算了 }void insert(int o,int l,int r,int val) {if(l <= tree[o].l && tree[o].r <= r){tree[o].nCover += val;tree[o].Update();return;}int mid = (tree[o].l + tree[o].r) >> 1;if(mid > l) insert(o<<1,l,r,val);if(mid < r) insert(o<<1|1,l,r,val);tree[o].Update(); }int bisearch(double x) {int l = 1,r = size,mid;while(l <= r){mid = (l + r) >> 1;if(fabs(edge[mid] - x) < eps)return mid;else if(x > edge[mid])l = mid + 1;else r = mid - 1;} }int main() {int t,n;cin >> t;while(t--){cin >> n;tmpsize = 0;vec.clear();for(int i = 1; i <= n; i++){double x0,x1,y0,y1;cin >> x0 >> y0 >> x1 >> y1;vec.push_back(Line(x0,y0,y1,1));vec.push_back(Line(x1,y0,y1,-1));tmp[tmpsize++] = y0;tmp[tmpsize++] = y1;}sort(vec.begin(),vec.end(),cmp);DiscretData();build(1,1,size);double ans = 0;for(int i = 0; i < vec.size(); i++){if(i > 0)ans += (vec[i].x - vec[i-1].x) * tree[1].yMore;int l = bisearch(vec[i].y1);int r = bisearch(vec[i].y2);insert(1,l,r,vec[i].val);}printf("%.2lf\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1255（线段树求重叠面积）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。