|
|
题目链接： http://poj.org/problem?id=1177
  /**//*
 题意：
给定N(N <= 5000)个矩形纸片，求它们重叠后外围轮廓的周长。
解法：
线段树
思路：
矩形面积并的变形，其实只需要修改Update函数即可，在线段树的
结点中保存一个nCover域，表示当前插入的线段覆盖的次数，yCount表
示当前y方向的长度的段数，LeftConnect和RightConnect表示当前结点
的线段两端点是否和父亲结点的区间的左右端点连接，之后的工作就是
在插入线段的时候随即更新这些信息就可以了。
然后统计周长的时候x方向和y方向都做一遍，其中一维线性枚举，
另一维通过线段树区间插入，外轮廓的周长就是每次相邻矩形统计的时
候 线段树根结点的段数*2*相邻矩形边的差 的总和。
Update函数的更新如下：
void Tree::Update() {
if(nCover) {
// 当前区间的线段被完全覆盖
yCount = 1;
LeftConnect = RightConnect = true;
}else {
if(l + 1 == r) {
// 叶子结点的区间，并且未被覆盖
yCount = 0;
LeftConnect = RightConnect = false;
}else {
// 内部结点所在区间，根据子树的情况统计信息
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;
}
|