|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1255
  /**//*
 題意：
給出N(N <= 1000)個矩形，求被覆蓋2次以上的矩形面積并。
解法：
離散化+線段樹
思路：
類似于覆蓋一次的矩形面積并問題，還是用線段樹求解，首先我們
將每個矩形的縱向邊投影到Y(jié)軸上，這樣就可以把矩形的縱向邊看成一個
閉區(qū)間，用線段樹來維護(hù)這些矩形邊的并。現(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和;
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define maxn 2200
double tmp[maxn], bin[maxn];
int tmpsize, size;
struct Tree  {
int p;
int l, r;
int nCover;
double ylenOnce, ylenMore;
  void Update() {
if(nCover > 1) {
ylenOnce = 0;
ylenMore = bin[r] - bin[l];
}else if(nCover == 1) {
ylenMore = T[p<<1].ylenMore + T[p<<1].ylenOnce
+ T[p<<1|1].ylenMore + T[p<<1|1].ylenOnce;
ylenOnce = (bin[r] - bin[l]) - ylenMore;
}else {
if(l + 1 == r) {
ylenOnce = ylenMore = 0;
}else {
ylenOnce = T[p<<1].ylenOnce + T[p<<1|1].ylenOnce;
ylenMore = T[p<<1].ylenMore + T[p<<1|1].ylenMore;
 }
}
}
}T[maxn*4];
struct VLine {
double x;
double y1, y2;
int val;
VLine() {}
VLine(double _x, double _y1, double _y2, int _v) {
x = _x;
y1 = _y1;
y2 = _y2;
val = _v;
}
};
vector < VLine > Vl;
bool cmp(VLine a, VLine b) {
return a.x < b.x;
}
void Process() {
sort(tmp, tmp + tmpsize);
bin[ size = 1 ] = tmp[0];
for(int i = 1; i < tmpsize; i++) {
if(fabs(tmp[i] - tmp[i-1]) > 1e-6)
bin[ ++size ] = tmp[i];
}
}
int Binary(double v) {
int l = 1;
int r = size;
while(l <= r) {
int m = (l + r) >> 1;
if(fabs(v - bin[m]) < 1e-6)
return m;
if(v > bin[m])
l = m + 1;
else
r = m - 1;
}
}
void Build(int p, int l, int r) {
T[p].l = l; T[p].r = r;
T[p].p = p;
T[p].nCover = 0; T[p].ylenOnce = T[p].ylenMore = 0;
if(l + 1 == r || l == r) {
return ;
}
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid, r);
}
void Insert(int p, int l, int r, int val) {
if(r <= T[p].l || l >= T[p].r)
return ;
if(l <= T[p].l && T[p].r <= r) {
T[p].nCover += val;
T[p].Update();
return ;
}
Insert(p<<1, l, r, val);
Insert(p<<1|1, l, r, val);
T[p].Update();
}
int n;
int main() {
int t;
int i;
scanf("%d", &t);
while(t--) {
tmpsize = 0;
Vl.clear();
scanf("%d", &n);
for(i = 0; i < n; i++) {
double x0, x1, y0, y1;
scanf("%lf %lf %lf %lf", &x0, &y0, &x1, &y1);
Vl.push_back(VLine(x0, y0, y1, 1));
Vl.push_back(VLine(x1, y0, y1, -1));
tmp[ tmpsize++ ] = y0;
tmp[ tmpsize++ ] = y1;
}
sort(Vl.begin(), Vl.end(), cmp);
Process();
Build(1, 1, size);
double ans = 0;
for(i = 0; i < Vl.size(); i++) {
if(i) {
ans += (Vl[i].x - Vl[i-1].x) * T[1].ylenMore;
}
int y1 = Binary(Vl[i].y1);
int y2 = Binary(Vl[i].y2);
if(y1 < y2)
Insert(1, y1, y2, Vl[i].val);
}
printf("%.2lf\n", ans);
}
return 0;
}
|