oyjpArt ACM/ICPC算法程序設計空間

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.

The corresponding boundary is the whole set of line segments drawn in Figure 2.

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.shnenglu.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
{
????Lines_tree? * ?lchild,? * ?rchild;
???? int ?m;? // 測度
???? int ?cnt;??? // count
???? int ?lines;? // 連續段數
???? int ?lbd,?rbd;? // 左右端點是否被覆蓋?
???? int ?f,?r;? // 左右端點
} ;
Lines_tree * ?root;
struct ?rec { int ?x,?y,?x1,?y1;} r[maxn];
struct ?Line
{
???? int ?x,?y1,?y2; int ?sign;
????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;

void ?make_tree( int ?a,? int ?b,?Lines_tree * ?node)
{
????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 )
???? {
????????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)
{
?????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)
{
???? 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)
{
???? if (a <= now -> f? && ?b >= now -> r)
????????now -> cnt ++ ;
???? if (now -> r - now -> f > 1 )
???? {
???????? 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)
{
???? if (a <= now -> f? && ?b >= now -> f)
???? {
???????? if (a == now -> f)?now -> lbd? = ? 0 ;
???????? if (b == now -> r)?now -> rbd? = ? 0 ;
????????now -> cnt -- ;
????}
???? if (now -> r - now -> f > 1 )
???? {
???????? 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)
{
???? return ?( * (Line * )a).x? - ?( * (Line * )b).x;??? // 這里不要寫成->
}

void ?init()
{
???? // initiation
???? // input
???? int ?i;
????scanf( " %d " ,? & nr);
???? for (i = 0 ;?i < nr;?i ++ )
???? {
????????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()
{
???? int ?nowM? = ? 0 ;
???? int ?nowLine? = ? 0 ;
???? int ?lastM? = ? 0 ;
???? int ?lastLine? = ? 0 ;
???? int ?i;
???? for (i = 0 ;?i < nr * 2 ;?i ++ )
???? {
???????? 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()
{
????printf( " %d\n " ,?ans);
}

int ?main()
{
// ????freopen("t.in",?"r",?stdin);
????make( - 10000 ,? 10000 );
????init();
????work();
????output();
???? return ? 0 ;
}