青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

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://m.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] [23] [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 ;
}

Feedback

# re: 線段樹測度與連續斷的應用 on IOI98 pictures  回復  更多評論   

2007-04-07 01:01 by
void del( int a, int b, Lines_tree * now)
{
if (a <= now -> f && b >= now -> f)


這個是不是有問題?
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            乱人伦精品视频在线观看| 亚洲激情偷拍| 亚洲女优在线| 国产毛片一区| 久久久久久久久久久成人| 久久久成人网| 亚洲国产一区二区三区在线播| 久久嫩草精品久久久久| 欧美一区二区视频在线观看2020| 国产精品免费看| 久久狠狠婷婷| 欧美成人一品| 亚洲欧美日韩国产成人精品影院 | 亚洲欧美综合精品久久成人| 亚洲欧美日韩网| 亚洲国产第一页| 一区二区三区国产在线观看| 国产亚洲免费的视频看| 欧美激情国产高清| 国产精品国产三级国产aⅴ9色| 久久久999精品| 蜜臀av在线播放一区二区三区| 一区二区三区毛片| 久久国产精品久久国产精品| 亚洲精品自在在线观看| 日韩午夜在线| 狠狠色狠狠色综合日日小说| 亚洲伦理网站| 激情成人综合| 亚洲一区二区伦理| 亚洲黄网站在线观看| 一区二区三区四区五区精品视频 | 欧美mv日韩mv亚洲| 欧美亚洲三区| 欧美成人日韩| 久久性天堂网| 国产精品欧美日韩一区二区| 亚洲国产精品va| 国产女主播一区二区| 亚洲国产欧美日韩| 狠狠入ady亚洲精品经典电影| 中日韩午夜理伦电影免费| 91久久国产综合久久91精品网站| 亚洲欧美日韩高清| 99亚洲一区二区| 噜噜噜在线观看免费视频日韩| 欧美一区二区视频网站| 欧美理论在线播放| 欧美波霸影院| 国产精品久久久对白| 亚洲激情国产精品| 亚洲经典一区| 免费观看一区| 欧美成人免费在线观看| 国内外成人免费视频| 在线亚洲自拍| 亚洲欧美日韩国产一区| 国产精品高潮呻吟久久| 亚洲另类视频| 正在播放亚洲一区| 欧美高清视频| 亚洲欧洲精品一区二区三区波多野1战4 | 99爱精品视频| 一区二区三区av| 欧美精品三区| 日韩视频在线观看一区二区| 99热在线精品观看| 欧美国产日韩在线| 91久久久亚洲精品| 99伊人成综合| 欧美视频网站| 午夜欧美大片免费观看| 欧美在线观看视频在线| 国产人成精品一区二区三| 先锋影院在线亚洲| 久久久噜噜噜久久| 好吊妞**欧美| 欧美激情视频一区二区三区免费 | 午夜精品久久久久久久| 久久婷婷麻豆| 亚洲美女精品一区| 国产精品国产自产拍高清av| 性色av一区二区三区在线观看| 久久亚洲私人国产精品va| 在线观看欧美| 欧美日韩在线三级| 香港成人在线视频| 欧美国产激情| 亚洲——在线| 国内成+人亚洲+欧美+综合在线| 久久综合精品国产一区二区三区| 亚洲欧洲一区二区三区| 亚洲欧美日韩国产综合| 国产在线精品一区二区夜色| 欧美精品色一区二区三区| 亚洲午夜日本在线观看| 久久综合色一综合色88| 中国女人久久久| 黄色日韩网站视频| 欧美日韩一区自拍| 久久久噜噜噜久噜久久| 亚洲免费成人av| 老色鬼久久亚洲一区二区| av成人国产| 极品少妇一区二区| 欧美日韩亚洲一区二区三区| 久久国产高清| 一区二区av| 欧美大片在线观看一区二区| 午夜精品一区二区三区在线视| 亚洲国产视频a| 国产日产高清欧美一区二区三区| 欧美成人一区二区三区| 欧美伊久线香蕉线新在线| 一区二区毛片| 亚洲高清不卡在线观看| 久久久久国产精品一区| 亚洲自拍偷拍麻豆| 亚洲激情网站| 极品尤物久久久av免费看| 国产精品色婷婷| 国产精品第一页第二页第三页| 欧美国产专区| 免播放器亚洲一区| 久久aⅴ国产紧身牛仔裤| 一个色综合av| 日韩一二三在线视频播| 男女激情视频一区| 久久久国产午夜精品| 午夜视频在线观看一区| 亚洲自拍偷拍一区| 亚洲视频导航| 99精品热视频| 一本色道**综合亚洲精品蜜桃冫| 在线观看欧美日本| 国内精品模特av私拍在线观看| 国产欧美日韩综合| 国产精品欧美一区喷水| 国产精品色在线| 国产欧美综合在线| 国产精品一区二区在线观看| 国产精品私房写真福利视频| 国产精品免费一区二区三区在线观看 | 亚洲午夜电影在线观看| 一本大道久久a久久精二百| 亚洲每日在线| 一区二区av在线| 亚洲一区二区欧美| 亚洲欧美日韩综合aⅴ视频| 亚洲综合色丁香婷婷六月图片| 亚洲一级片在线观看| 亚洲欧美日韩国产综合| 欧美在线你懂的| 久久欧美中文字幕| 欧美国产一区在线| 亚洲精品一区二区网址| 一本大道久久a久久综合婷婷| 一区二区日韩欧美| 亚洲欧美中文日韩v在线观看| 欧美在线视频全部完| 久久久久久久成人| 欧美电影免费观看网站| 国产精品va在线播放| 国模吧视频一区| 亚洲精品欧美激情| 亚洲自拍啪啪| 另类专区欧美制服同性| 亚洲老板91色精品久久| 亚洲欧美激情视频| 久久久噜噜噜久久| 欧美精品久久一区| 国产精品一区二区三区久久久| 在线精品国产成人综合| 在线视频欧美精品| 久久精品国产视频| 亚洲国产精品成人va在线观看| 在线视频亚洲| 久久香蕉国产线看观看av| 欧美午夜一区二区三区免费大片| 国模大胆一区二区三区| 日韩小视频在线观看专区| 久久精品免费看| 亚洲乱码国产乱码精品精| 午夜精品影院| 欧美日韩1区2区| 激情综合亚洲| 亚洲免费影院| 亚洲国产成人tv| 久久国产精品高清| 国产精品久久久久久久久婷婷 | 国产日韩专区| 中文国产成人精品| 美女图片一区二区| 亚洲一区二区三区欧美| 免费在线看一区| 伊人久久大香线| 久久激情久久| 亚洲深夜影院| 欧美日韩免费一区| 亚洲精品1区2区|