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

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

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

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

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

這里我們?cè)偌由蠝y(cè)度與連續(xù)段的作用：

(一)、?? 測(cè)度

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

?

?

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

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

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

?

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

Procedure? Lines_Tree.UpData

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

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

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

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

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

UpData 的復(fù)雜度為 O(1) ，則用 UpData 來(lái)動(dòng)態(tài)維護(hù)測(cè)度后執(zhí)行根結(jié)點(diǎn)的 Insert 與 Delete 的復(fù)雜度仍為 O(logN) 。

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

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

?

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

lbd? =?

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

?

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

rbd? =?

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

?

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

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

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

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

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

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

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

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

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

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

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

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

?

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

Procedure? Lines_Tree.UpData’

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

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

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

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

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

6??????? ??????????then? lbd?? ? ? 0?? { 進(jìn)行到這一步，如果為葉結(jié)點(diǎn)，
??????????????????????????????????????????????? count = 0}

7??????? ????????????????rbd? ? ? 0

8??????? ????????????????line? ? ? 0

9??????? ??????????else? line? ? ?? Leftchild ↑ .line? +? Rightchild ↑ .line? -?

????????????????????????????? Leftchild ↑ .rbd * Rightchild ↑ .lbd

{ 用乘法確定 Leftchild ↑ .rbd 與 Rightchild ↑ .lbd 是否同時(shí)為 1}

?

于是我按下面的步驟重寫了程序：

1.??????? 以矩形頂點(diǎn)坐標(biāo)切割平面，實(shí)現(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? 事件的最大編號(hào)

8.??????? ??do?? if? I 是插入事件

9.??????? ??????????then? Root.Insert(Y_Map.Coord[ 事件線段頂點(diǎn) 1] ，
???????????????????????? Y_Map.Coord[ 事件線段頂點(diǎn) 2])

10.??? ??????????else? Root.Delete(Y_Map.Coord[ 事件線段頂點(diǎn) 1] ，
?????????????????? ? ??????Y_Map.Coord[ 事件線段頂點(diǎn) 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 ;
// 寫一個(gè)線段樹(shù)的過(guò)程
struct ?Lines_tree
{
????Lines_tree? * ?lchild,? * ?rchild;
???? int ?m;? // 測(cè)度
???? int ?cnt;??? // count
???? int ?lines;? // 連續(xù)段數(shù)
???? int ?lbd,?rbd;? // 左右端點(diǎn)是否被覆蓋?
???? int ?f,?r;? // 左右端點(diǎn)
} ;
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的計(jì)算都在這個(gè)里面！
{
???? 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 ;
}