oyjpArt ACM/ICPC算法程序設(shè)計空間

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

做這道題之前我用線段樹的結(jié)構(gòu)過了幾個題目 效果沒有我想象的好
但是這道題明顯就出了差距 直接離散化與用線段樹來做效果差了有將近10倍！

線段樹的基本應(yīng)用：請參考這篇文章

http://www.shnenglu.com/sicheng/archive/2006/11/24/15640.html

這里我們再加上測度與連續(xù)段的作用：

(一)、?? 測度

由于線段樹結(jié)構(gòu)遞歸定義，其測度也可以遞歸定義。增加數(shù)據(jù)域 Lines_Tree.M 表示以該結(jié)點為根的子樹的測度。 M 取值如下：

?

?

???????? a[j] – a[i] ?? 該結(jié)點 Count>0

M? =??? 0???????? ? 該結(jié)點為葉結(jié)點且 Count=0

???????? Leftchild ↑ .M + Rightchild ↑ .M ? 該結(jié)點為內(nèi)部結(jié)點且 Count=0

?

據(jù)此，可以用 Lines_Tree.UpData 來動態(tài)地維護 Lines_Tree.M 。 UpData 在每一次執(zhí)行 Insert 或 Delete 之后執(zhí)行。定義如下：

Procedure? Lines_Tree.UpData

1??????? if? count? >? 0

2??????? ??then? M? ? ? a[j]? –? [i]????? { 蓋滿區(qū)間，測度為 a[j] – a[i]}

3??????? ??else? if? j? -? i? =? 1 ????????{ 是否葉結(jié)點 }

4??????? ??????????then? M? ? ? 0 ??????{ 該結(jié)點是葉結(jié)點 }

5??????? ??????????else? M? ? ? Leftchild ↑ .M? +? Rightchild ↑ .M
????????????????????????????????????????? ?{ 內(nèi)部結(jié)點 }

UpData 的復(fù)雜度為 O(1) ，則用 UpData 來動態(tài)維護測度后執(zhí)行根結(jié)點的 Insert 與 Delete 的復(fù)雜度仍為 O(logN) 。

(二)、?? 連續(xù)段數(shù)

這里的連續(xù)段數(shù)指的是區(qū)間的并可以分解為多少個獨立的區(qū)間。如 [1 ， 2] ∪[2，3]∪ [5 ， 6] 可以分解為兩個區(qū)間 [1 ， 3] 與 [5 ， 6] ，則連續(xù)段數(shù)為 2 。增加一個數(shù)據(jù)域 Lines_Tree.line 表示該結(jié)點的連續(xù)段數(shù)。 Line 的討論比較復(fù)雜，內(nèi)部結(jié)點不能簡單地將左右孩子的 Line 相加。所以再增加 Lines_Tree.lbd 與 Lines_Tree.rbd 域。定義如下：

?

???????? 1??? 左端點 I 被描述區(qū)間蓋到

lbd? =?

???????? 0? ?? 左端點 I 不被描述區(qū)間蓋到

?

???????? 1???? 右端點 J 被描述區(qū)間蓋到

rbd? =?

??????? ?0 ???? 右端點 J 不被描述區(qū)間蓋到

?

lbd 與 rbd 的實現(xiàn)：

????????? 1? 該結(jié)點 count > 0

lbd? =??? 0? 該結(jié)點是葉結(jié)點且 count = 0

????????? leftchild ↑ .lbd??? 該結(jié)點是內(nèi)部結(jié)點且 Count=0

? ????????1? 該結(jié)點 count > 0

rbd? =??? 0? 該結(jié)點是葉結(jié)點且 count = 0

????????? rightchild ↑ .rbd?? 該結(jié)點是內(nèi)部結(jié)點且 Count=0

有了 lbd 與 rbd ， Line 域就可以定義了：

??????? 1? 該結(jié)點 count > 0

Line =?? 0? 該結(jié)點是葉結(jié)點且 count = 0

??????? ?Leftchild ↑ .Line? +? Rightchild ↑ .Line? -? 1
???????? 當(dāng)該結(jié)點是內(nèi)部結(jié)點且 Count=0 ， Leftchild ↑ .rbd = 1 且 Rightchild ↑ .lbd = 1

???????? Leftchild ↑ .Line? +? Rightchild ↑ .Line??
??? ????? 當(dāng)該結(jié)點是內(nèi)部結(jié)點且 Count=0 ， Leftchild ↑ .rbd 與 Rightchild ↑ .lbd 不都為 1

?

據(jù)此，可以定義 UpData’ 動態(tài)地維護 Line 域。與 UpData 相似， UpData’ 也在每一次執(zhí)行 Insert 或 Delete 后執(zhí)行。定義如下：

Procedure? Lines_Tree.UpData’

1??????? if? count? >? 0 ??????????{ 是否蓋滿結(jié)點表示的區(qū)間 }

2??????? ??then? lbd?? ? ? 1

3??????? ???????rbd?? ? ? 1

4??????? ???????Line? ? ? 1

5??????? ??else? if? ?j? -? i? =? 1???? { 是否為葉結(jié)點 }

6??????? ??????????then? lbd?? ? ? 0?? { 進行到這一步，如果為葉結(jié)點，
??????????????????????????????????????????????? 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.??????? 以矩形頂點坐標(biāo)切割平面，實現(xiàn)橫縱坐標(biāo)的離散化并建立映射 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;? // 連續(xù)段數(shù)
???? 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 ;
}