Picture
Time Limit:2000MS Memory Limit:10000K
Total Submit:742 Accepted:411
Description
A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.
Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.
![](http://acm.pku.edu.cn/JudgeOnline/images/1177_1.jpg)
The corresponding boundary is the whole set of line segments drawn in Figure 2.
![](http://acm.pku.edu.cn/JudgeOnline/images/1177_2.jpg)
The vertices of all rectangles have integer coordinates.
Input
Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.
0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.
Output
Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.
Sample Input
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
Sample Output
228
Source
IOI 1998
做这道题之前我用线段树的结构过了几个题目 效果没有我想象的好
但是这道题明显就出了差距 直接离散化与用线段树来做效果差了有将近10倍!
线段树的基本应用:请参考这篇文章
http://www.cppblog.com/sicheng/archive/2006/11/24/15640.html
这里我们再加上测度与连续段的作用:
(一)、
测度
由于线段树结构递归定义,其测度也可以递归定义。增加数据域
Lines_Tree.M
表示以该结点为根的子树的测度。
M
取值如下:
a[j] – a[i]
该结点
Count>0
M = 0
该结点为叶结点且
Count=0
Leftchild
↑
.M + Rightchild
↑
.M
该结点为内部结点且
Count=0
据此,可以用
Lines_Tree.UpData
来动态地维护
Lines_Tree.M
。
UpData
在每一次执行
Insert
或
Delete
之后执行。定义如下:
Procedure Lines_Tree.UpData
1
if count > 0
2
then M
ß
a[j] – [i] {
盖满区间,测度为
a[j] – a[i]}
3
else if j - i = 1 {
是否叶结点
}
4
then M
ß
0 {
该结点是叶结点
}
5
else M
ß
Leftchild
↑
.M + Rightchild
↑
.M
{
内部结点
}
UpData
的复杂度为
O(1)
,则用
UpData
来动态维护测度后执行根结点的
Insert
与
Delete
的复杂度仍为
O(logN)
。
(二)、
连续段数
这里的连续段数指的是区间的并可以分解为多少个独立的区间。如
[1
,
2]
∪[2,3]∪
[5
,
6]
可以分解为两个区间
[1
,
3]
与
[5
,
6]
,则连续段数为
2
。增加一个数据域
Lines_Tree.line
表示该结点的连续段数。
Line
的讨论比较复杂,内部结点不能简单地将左右孩子的
Line
相加。所以再增加
Lines_Tree.lbd
与
Lines_Tree.rbd
域。定义如下:
1
左端点
I
被描述区间盖到
lbd =
0
左端点
I
不被描述区间盖到
1
右端点
J
被描述区间盖到
rbd =
0
右端点
J
不被描述区间盖到
lbd
与
rbd
的实现:
1
该结点
count > 0
lbd = 0
该结点是叶结点且
count = 0
leftchild
↑
.lbd
该结点是内部结点且
Count=0
1
该结点
count > 0
rbd = 0
该结点是叶结点且
count = 0
rightchild
↑
.rbd
该结点是内部结点且
Count=0
有了
lbd
与
rbd
,
Line
域就可以定义了:
1
该结点
count > 0
Line = 0
该结点是叶结点且
count = 0
Leftchild
↑
.Line + Rightchild
↑
.Line - 1
当该结点是内部结点且
Count=0
,
Leftchild
↑
.rbd = 1
且
Rightchild
↑
.lbd = 1
Leftchild
↑
.Line + Rightchild
↑
.Line
当该结点是内部结点且
Count=0
,
Leftchild
↑
.rbd
与
Rightchild
↑
.lbd
不都为
1
据此,可以定义
UpData’
动态地维护
Line
域。与
UpData
相似,
UpData’
也在每一次执行
Insert
或
Delete
后执行。定义如下:
Procedure Lines_Tree.UpData’
1
if count > 0 {
是否盖满结点表示的区间
}
2
then lbd
ß
1
3
rbd
ß
1
4
Line
ß
1
5
else if j - i = 1 {
是否为叶结点
}
6
then lbd
ß
0 {
进行到这一步,如果为叶结点,
count = 0}
7
rbd
ß
0
8
line
ß
0
9
else line
ß
Leftchild
↑
.line + Rightchild
↑
.line -
Leftchild
↑
.rbd * Rightchild
↑
.lbd
{
用乘法确定
Leftchild
↑
.rbd
与
Rightchild
↑
.lbd
是否同时为
1}
于是我按下面的步骤重写了程序:
1.
以矩形顶点坐标切割平面,实现横纵坐标的离散化并建立映射
X_Map
、
Y_Map
。
2.
事件排序
3.
Root.Build(1, N*2)
4.
Nowm
ß
0
5.
NowLine
ß
0
6.
Ans
ß
0
7.
for I
ß
1 to
事件的最大编号
8.
do if I
是插入事件
9.
then Root.Insert(Y_Map.Coord[
事件线段顶点
1]
,
Y_Map.Coord[
事件线段顶点
2])
10.
else Root.Delete(Y_Map.Coord[
事件线段顶点
1]
,
Y_Map.Coord[
事件线段顶点
2])
11.
nowM
ß
Root.M
12.
nowLine
ß
Root.Line
13.
ans
ß
ans + lastLine * 2 * (X_Map[I] – Y_Map[I-1])
14.
ans
ß
ans + |nowM – lastM|
15.
lasM
ß
nowM
16.
lastLine
ß
nowLine
参考论文《IOI98试题PICTURE谈起 陈宏》
#include
<
stdio.h
>
#include
<
stdlib.h
>
const
int
maxn
=
5010
;
//
写一个线段树的过程
struct
Lines_tree
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
Lines_tree
*
lchild,
*
rchild;
int
m;
//
测度
int
cnt;
//
count
int
lines;
//
连续段数
int
lbd, rbd;
//
左右端点是否被覆盖
int
f, r;
//
左右端点
}
;
Lines_tree
*
root;
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct
rec
{
int
x, y, x1, y1;}
r[maxn];
struct
Line
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
x, y1, y2;
int
sign;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Line(
int
a,
int
b,
int
c,
int
d):x(a), y1(b), y2(c), sign(d)
{}
Line(
void
):x(
0
),y1(
0
),y2(
0
),sign(
0
)
{}
}
line[
2
*
maxn
+
10
];
int
nr;
int
ans;
![](/Images/OutliningIndicators/None.gif)
void
make_tree(
int
a,
int
b, Lines_tree
*
node)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
node
->
lines
=
0
; node
->
m
=
0
; node
->
cnt
=
0
;
node
->
lbd
=
0
; node
->
rbd
=
0
;
node
->
lchild
=
NULL; node
->
rchild
=
NULL;
node
->
f
=
a; node
->
r
=
b;
if
(b
-
a
>
1
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
node
->
lchild
=
new
Lines_tree;
make_tree(a, (a
+
b)
/
2
, node
->
lchild);
node
->
rchild
=
new
Lines_tree;
make_tree((a
+
b)
/
2
, b, node
->
rchild);
}
}
void
make(
int
a,
int
b)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
root
=
new
Lines_tree;
make_tree(a, b, root);
}
void
update(Lines_tree
*
now)
//
lbd, rbd, m的计算都在这个里面!
{
if
(now
->
cnt
>
0
) now
->
m
=
now
->
r
-
now
->
f;
else
if
(now
->
r
==
now
->
f
+
1
) now
->
m
=
0
;
else
now
->
m
=
now
->
lchild
->
m
+
now
->
rchild
->
m;
}
void
update2(Lines_tree
*
now)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if
(now
->
cnt
>
0
)
{ now
->
lbd
=
1
; now
->
rbd
=
1
; now
->
lines
=
1
; }
else
if
(now
->
f
+
1
==
now
->
r)
{now
->
lbd
=
0
; now
->
rbd
=
0
; now
->
lines
=
0
;}
else
{
now
->
lbd
=
now
->
lchild
->
lbd; now
->
rbd
=
now
->
rchild
->
rbd;
now
->
lines
=
now
->
lchild
->
lines
+
now
->
rchild
->
lines
-
now
->
lchild
->
rbd
*
now
->
rchild
->
lbd;
}
}
void
insert(
int
a,
int
b, Lines_tree
*
now)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
if
(a
<=
now
->
f
&&
b
>=
now
->
r)
now
->
cnt
++
;
if
(now
->
r
-
now
->
f
>
1
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
(a
<
(now
->
f
+
now
->
r)
/
2
) insert(a, b, now
->
lchild);
if
(b
>
(now
->
f
+
now
->
r)
/
2
) insert(a, b, now
->
rchild);
}
update(now);
update2(now);
}
void
del(
int
a,
int
b, Lines_tree
*
now)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
if
(a
<=
now
->
f
&&
b
>=
now
->
f)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
(a
==
now
->
f) now
->
lbd
=
0
;
if
(b
==
now
->
r) now
->
rbd
=
0
;
now
->
cnt
--
;
}
if
(now
->
r
-
now
->
f
>
1
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
(a
<
(now
->
f
+
now
->
r)
/
2
) del(a, b, now
->
lchild);
if
(b
>
(now
->
f
+
now
->
r)
/
2
) del(a, b, now
->
rchild);
}
update(now);
update2(now);
}
int
cmp(
const
void
*
a,
const
void
*
b)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
return
(
*
(Line
*
)a).x
-
(
*
(Line
*
)b).x;
//
这里不要写成->
}
void
init()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
//
initiation
//
input
int
i;
scanf(
"
%d
"
,
&
nr);
for
(i
=
0
; i
<
nr; i
++
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf(
"
%d%d%d%d
"
,
&
r[i].x,
&
r[i].y,
&
r[i].x1,
&
r[i].y1);
line[
2
*
i]
=
Line(r[i].x, r[i].y, r[i].y1,
0
);
line[
2
*
i
+
1
]
=
Line(r[i].x1, r[i].y, r[i].y1,
1
);
}
qsort(line, nr
*
2
,
sizeof
(line[
0
]), cmp);
//
pretreatment
}
void
work()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
nowM
=
0
;
int
nowLine
=
0
;
int
lastM
=
0
;
int
lastLine
=
0
;
int
i;
for
(i
=
0
; i
<
nr
*
2
; i
++
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
(line[i].sign
==
0
)
insert(line[i].y1, line[i].y2, root);
else
del(line[i].y1, line[i].y2, root);
nowM
=
root
->
m;
nowLine
=
root
->
lines;
ans
+=
lastLine
*
2
*
(line[i].x
-
line[i
-
1
].x);
ans
+=
abs(nowM
-
lastM);
lastM
=
nowM;
lastLine
=
nowLine;
}
}
void
output()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
printf(
"
%d\n
"
, ans);
}
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
//
freopen("t.in", "r", stdin);
make(
-
10000
,
10000
);
init();
work();
output();
return
0
;
}