|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3265
  /**//*
 題意：
給定N(N <= 50000)個(gè)中空的矩形紙片，求它們面積并。
解法：
離散化+線(xiàn)段樹(shù)
思路：
2010年寧波區(qū)域賽的題，就是矩形面積并的一個(gè)變形，轉(zhuǎn)化很容
易想到，將中空的矩形紙片分割成四個(gè)小的矩形然后求N*4個(gè)矩形的
面積并即可。
再總結(jié)一下矩形面積并的nlog(n)經(jīng)典算法吧。首先我們將每個(gè)矩
形的縱向邊投影到Y(jié)軸上，這樣就可以把矩形的縱向邊看成一個(gè)閉區(qū)間
，用線(xiàn)段樹(shù)來(lái)維護(hù)這些矩形邊的并。現(xiàn)在求的是矩形的面積并，于是可
以枚舉矩形的x坐標(biāo)，然后檢測(cè)當(dāng)前相鄰x坐標(biāo)上y方向的合法長(zhǎng)度，兩
者相乘就是其中一塊面積，枚舉完畢后就求得了所有矩形的面積并。
我的線(xiàn)段樹(shù)結(jié)點(diǎn)描述保存了以下信息：區(qū)間的左右端點(diǎn)、結(jié)點(diǎn)所在
數(shù)組編號(hào)（因?yàn)椴捎渺o態(tài)結(jié)點(diǎn)可以大大節(jié)省申請(qǐng)空間的時(shí)間）、該結(jié)點(diǎn)
被豎直線(xiàn)段完全覆蓋的次數(shù)Cover和當(dāng)前結(jié)點(diǎn)的測(cè)度。測(cè)度是指相鄰x坐
標(biāo)之間有效的y方向的長(zhǎng)度的和（要求在該區(qū)間內(nèi)）。于是重點(diǎn)就在于
如何維護(hù)測(cè)度，我們將一個(gè)矩形分成兩條豎直線(xiàn)段來(lái)存儲(chǔ)，左邊的邊稱(chēng)
為入邊，右邊的邊則為出邊，然后把所有這些豎直線(xiàn)段按照x坐標(biāo)遞增排
序，每次進(jìn)行插入操作，因?yàn)樽鴺?biāo)有可能不是整數(shù)，所以必須在做這些
之前將y方向的坐標(biāo)離散化到數(shù)組中，每次插入時(shí)如果當(dāng)前區(qū)間被完全覆
蓋，那么就要對(duì)Cover域進(jìn)行更新，入邊+1，出邊-1。更新完畢后判斷當(dāng)
前結(jié)點(diǎn)的Cover域是否大于零，如果大于零那么當(dāng)前節(jié)點(diǎn)的測(cè)度就是結(jié)點(diǎn)
管理區(qū)間在y軸上的實(shí)際長(zhǎng)度，否則，如果是葉子節(jié)點(diǎn)，那么測(cè)度為0，
如果是內(nèi)部結(jié)點(diǎn)，那么測(cè)度的值是左右兒子測(cè)度的和。這個(gè)更新是log(n)
的，所以，總的復(fù)雜度就是nlog(n)。
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef int Type;
#define ll __int64
#define maxn 200200
// 垂直線(xiàn)段
struct VLine  {
Type x;
Type y1, y2;
int val;
  VLine() {}
VLine(int _x, int _y1, int _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;
}
// 矩形
struct Rectangle {
int x0, y0, x1, y1;
Rectangle() {}
Rectangle(int _x0, int _y0, int _x1, int _y1) {
x0 = _x0; y0 = _y0;
x1 = _x1; y1 = _y1;
}
};
vector <Rectangle> Rec;
int tmp[maxn], tmpsize;
int bin[maxn], size;
struct Tree {
int p;
int l, r;
int nCover; // 被完全覆蓋的次數(shù)
Type ylen; // 測(cè)度
void Update() {
if(nCover > 0)
ylen = bin[r] - bin[l];
else {
if(l + 1 == r)
ylen = 0;
else {
ylen = T[p<<1].ylen + T[p<<1|1].ylen;
}
}
}
int Mid() {
return (l + r) >> 1;
}
}T[maxn*4];
void Build(int p, int l, int r) {
T[p].l = l;
T[p].r = r;
T[p].p = p;
T[p].ylen = T[p].nCover = 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(l <= T[p].l && T[p].r <= r) {
T[p].nCover += val;
T[p].Update();
return ;
}
int mid = T[p].Mid();
if(l < mid) {
Insert(p<<1, l, r, val);
}
if(mid < r) {
Insert(p<<1|1, l, r, val);
}
T[p].Update();
}
void ProcessBinArray() {
sort(tmp, tmp + tmpsize);
bin[size = 1] = tmp[0];
int i;
for(i = 1; i < tmpsize; i++) {
if(tmp[i] != tmp[i-1])
bin[++size] = tmp[i];
}
}
int Binary(int v) {
int l = 1;
int r = size;
while(l <= r) {
int m = (l + r) >> 1;
if(bin[m] == v)
return m;
if(v > bin[m]) {
l = m + 1;
}else
r = m - 1;
}
}
int main() {
int n;
int i, j;
Type x[4], y[4];
while(scanf("%d", &n) != EOF && n) {
Rec.clear();
Vl.clear();
tmpsize = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < 4; j++) {
scanf("%d %d", &x[j], &y[j]);
tmp[ tmpsize++ ] = y[j];
}
Rec.push_back(Rectangle(x[0], y[0], x[2], y[1]));
Rec.push_back(Rectangle(x[2], y[0], x[3], y[2]));
Rec.push_back(Rectangle(x[2], y[3], x[3], y[1]));
Rec.push_back(Rectangle(x[3], y[0], x[1], y[1]));
}
ProcessBinArray();
for(i = 0; i < Rec.size(); i++) {
Rectangle& rt = Rec[i];
if(rt.x0 == rt.x1 || rt.y0 == rt.y1)
continue;
int y0 = Binary(rt.y0);
int y1 = Binary(rt.y1);
Vl.push_back(VLine(rt.x0, y0, y1, 1));
Vl.push_back(VLine(rt.x1, y0, y1, -1));
}
sort(Vl.begin(), Vl.end(), cmp);
Build(1, 1, size);
ll ans = 0;
for(i = 0; i < Vl.size(); i++) {
if(i) {
ans += (ll)(Vl[i].x - Vl[i-1].x) * T[1].ylen;
}
Insert(1, Vl[i].y1, Vl[i].y2, Vl[i].val);
}
printf("%I64d\n", ans);
}
return 0;
}
|