• <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>

            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)


            這個是不是有問題?
            女同久久| 久久久久人妻一区精品色| 91亚洲国产成人久久精品| 久久精品国产欧美日韩| 久久久久精品国产亚洲AV无码| 久久天天躁夜夜躁狠狠| 精品久久久久久中文字幕人妻最新| 国产V亚洲V天堂无码久久久| 久久综合伊人77777麻豆| 午夜不卡久久精品无码免费| 欧美与黑人午夜性猛交久久久| 久久w5ww成w人免费| 久久精品国产欧美日韩| 91久久香蕉国产熟女线看| 久久久久久久久久久| 精品久久综合1区2区3区激情| 久久Av无码精品人妻系列 | 久久精品国产只有精品2020| 香蕉久久AⅤ一区二区三区| 91精品观看91久久久久久| 嫩草伊人久久精品少妇AV| 思思久久99热免费精品6| 久久伊人精品青青草原高清| 久久一日本道色综合久久| 91麻豆国产精品91久久久| 天堂无码久久综合东京热| 国产巨作麻豆欧美亚洲综合久久| 久久精品国产影库免费看| 亚洲乱亚洲乱淫久久| 久久国产精品久久国产精品| 久久精品水蜜桃av综合天堂| 无码精品久久久天天影视 | 国产高潮国产高潮久久久| A级毛片无码久久精品免费| 中文字幕亚洲综合久久菠萝蜜 | 无码国产69精品久久久久网站| 三级片免费观看久久| 伊人久久大香线蕉亚洲五月天| 色妞色综合久久夜夜| 99久久er这里只有精品18| 久久九九亚洲精品|