|
|
題目鏈接： http://poj.org/problem?id=1177
  /**//*
 題意：
給定N(N <= 5000)個(gè)矩形紙片，求它們重疊后外圍輪廓的周長。
解法：
線段樹
思路：
矩形面積并的變形，其實(shí)只需要修改Update函數(shù)即可，在線段樹的
結(jié)點(diǎn)中保存一個(gè)nCover域，表示當(dāng)前插入的線段覆蓋的次數(shù)，yCount表
示當(dāng)前y方向的長度的段數(shù)，LeftConnect和RightConnect表示當(dāng)前結(jié)點(diǎn)
的線段兩端點(diǎn)是否和父親結(jié)點(diǎn)的區(qū)間的左右端點(diǎn)連接，之后的工作就是
在插入線段的時(shí)候隨即更新這些信息就可以了。
然后統(tǒng)計(jì)周長的時(shí)候x方向和y方向都做一遍，其中一維線性枚舉，
另一維通過線段樹區(qū)間插入，外輪廓的周長就是每次相鄰矩形統(tǒng)計(jì)的時(shí)
候 線段樹根結(jié)點(diǎn)的段數(shù)*2*相鄰矩形邊的差 的總和。
Update函數(shù)的更新如下：
void Tree::Update() {
if(nCover) {
// 當(dāng)前區(qū)間的線段被完全覆蓋
yCount = 1;
LeftConnect = RightConnect = true;
}else {
if(l + 1 == r) {
// 葉子結(jié)點(diǎn)的區(qū)間，并且未被覆蓋
yCount = 0;
LeftConnect = RightConnect = false;
}else {
// 內(nèi)部結(jié)點(diǎn)所在區(qū)間，根據(jù)子樹的情況統(tǒng)計(jì)信息
LeftConnect = T[root<<1].LeftConnect;
RightConnect = T[root<<1|1].RightConnect;
yCount = T[root<<1].yCount + T[root<<1|1].yCount -
((T[root<<1|1].LeftConnect*T[root<<1].RightConnect)?1:0);
}
}
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 20010
struct VLine  {
int x;
int y0, y1;
int val;
  VLine() {}
VLine(int _x, int _y0, int _y1, int _val) {
x = _x;
y0 = _y0;
y1 = _y1;
val = _val;
 }
};
vector <VLine> Vl[2];
bool cmp(VLine a, VLine b) {
return a.x < b.x;
}
struct Tree {
int root, l, r;
int nCover;
int ylen;
int yCount;
bool LeftConnect, RightConnect;
void Update();
}T[ maxn*4 ];
void Tree::Update() {
if(nCover) {
ylen = r - l;
yCount = 1;
LeftConnect = RightConnect = true;
}else {
if(l + 1 == r) {
ylen = 0;
yCount = 0;
LeftConnect = RightConnect = false;
}else {
ylen = T[root<<1].ylen + T[root<<1|1].ylen;
LeftConnect = T[root<<1].LeftConnect;
RightConnect = T[root<<1|1].RightConnect;
yCount = T[root<<1].yCount + T[root<<1|1].yCount -
((T[root<<1|1].LeftConnect*T[root<<1].RightConnect)?1:0);
}
}
}
void Build(int root, int l, int r) {
T[root].l = l;
T[root].r = r;
T[root].root = root;
T[root].nCover = T[root].ylen = T[root].yCount = 0;
T[root].LeftConnect = T[root].RightConnect = false;
if(l + 1 == r) {
return ;
}
int mid = (l + r) >> 1;
Build(root<<1, l, mid);
Build(root<<1|1, mid, r);
}
void Insert(int root, int l, int r, int val) {
if(T[root].l >= r || l >= T[root].r)
return ;
if(l <= T[root].l && T[root].r <= r) {
T[root].nCover += val;
T[root].Update();
return ;
}
Insert(root<<1, l, r, val);
Insert(root<<1|1, l, r, val);
T[root].Update();
}
int n;
int main() {
int i, j;
while(scanf("%d", &n) != EOF) {
Vl[0].clear();
Vl[1].clear();
for(i = 0; i < n; i++) {
int x0, y0, x1, y1;
scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
x0 += 10000; y0 += 10000;
x1 += 10000; y1 += 10000;
Vl[0].push_back( VLine(x0, y0, y1, 1) );
Vl[0].push_back( VLine(x1, y0, y1, -1) );
Vl[1].push_back( VLine(y0, x0, x1, 1) );
Vl[1].push_back( VLine(y1, x0, x1, -1) );
}
int ans = 0;
for(j = 0; j < 2; j++) {
sort(Vl[j].begin(), Vl[j].end(), cmp);
Build(1, 0, 20000);
for(i = 0; i < Vl[j].size(); i++) {
if(i) {
ans += 2 * (Vl[j][i].x - Vl[j][i-1].x) * T[1].yCount;
}
Insert(1, Vl[j][i].y0, Vl[j][i].y1, Vl[j][i].val);
}
}
printf("%d\n", ans);
}
return 0;
}
|