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

            Why so serious? --[NKU]schindlerlee

            2010年02月21日星期日.sgu177 平面四叉樹

            2010年02月21日星期日.sgu177 平面四叉樹
            This is my first problem solving report in English,sorry for my poor English.

            sgu177: I know 3 ways to solve this problem.
            1.quad tree of plane :this is a good and straight forward solution
            2.segment trees covers segment trees :less efficient than quadtree,but easy to implement
            3.with the special characteristic of this problem,we can dye the plane with opposite
            order of the input,and if one grid is colored it cannot be colored again.

            The 1st solution can be used extensively.
            Quite a lot of the plane query problem can be solve by it.And it also have more
            applications in real, such as 3D game programming,computational geometry.

            So if you don't know it,I suggest you look the code below.It will be helpful
            Though the solution is quite slow in this problem....

            The 3rd solution is very smart,you can look here
            http://www.briefdream.com/sgu-177/
            for a complete code.

            I think the original intention of this problem is to practice quadtree,the memory is
            just OK when I used quadtree.

            sgu177:就我所知,此題有3中解法。
            1.平面四叉樹:這是一個平面問題的直覺通解。
            2.線段樹套樹,更好寫一點,效率稍差,只是常數級別的差距。
            3.倒序染色。從后向前染色,如果一個格子已經被染過色的,那么就不必再被染第二遍。
            利用這個性質,可以得到一個聰明的解法。具體代碼看這里。
            http://www.briefdream.com/sgu-177/

            我認為這題的本意就是為了練習一下四叉樹,四叉樹再平面詢問的問題上,可以有非常多的應用。
            有些需要很巧妙的思考的問題可以直接用四叉樹暴力。
            而且四叉樹在編碼,計算幾何,計算機圖形學,游戲編程上都有很廣泛的應用,有可能的話,我
            建議自己實現一下。

            本題內存比較緊,int超內存的話,可以用short搞一下。

            ?1?
            ?2?const?int?N?=?1001;
            ?3?struct?node?{
            ?4?????short?ux,?uy,?dx,?dy;
            ?5?????char?c;
            ?6?????node?*pt[4];
            ?7?}?pool[N?*?N?*?2],?*root;
            ?8??
            ?9?int?top,?n,?m;
            10?void?build(node?*?root,?short?ux,?short?uy,?short?dx,?short?dy)
            11?{
            12???//root->c?=?0;
            13???root->ux?=?ux;
            14???root->uy?=?uy;
            15???root->dx?=?dx;
            16???root->dy?=?dy;
            17???if?(ux?==?dx?&&?uy?==?dy)?{?return;?}
            18?
            19???short?mx?=(ux?+?dx)?>>?1;
            20???short?my?=(uy?+?dy)?>>?1;
            21???build(root->pt[0]?=?&pool[top++],?ux,?uy,?mx,?my);
            22???if?(uy?!=?dy)?{?build(root->pt[1]?=?&pool[top++],?ux,?my?+?1,?mx,?dy);?}
            23???if?(ux?!=?dx)?{?build(root->pt[2]?=?&pool[top++],?mx?+?1,?uy,?dx,?my);?}
            24???if?(ux?!=?dx?&&?uy?!=?dy)?{
            25???????build(root->pt[3]?=?&pool[top++],?mx?+?1,?my?+?1,?dx,?dy);
            26???}
            27?}
            28?
            29?char?color;
            30?int?x0,x1,y0,y1;
            31?const?int?NEG?=?2;
            32?void?dye(node?*?root)
            33?{
            34???if?(root?==?0)?{?return;?}
            35???if?(x0?>?root->dx?||?x1?<?root->ux?||
            36???????y0?>?root->dy?||?y1?<?root->uy)?{?//fast?exclude
            37???????return;
            38???}
            39???if?(x0?<=?root->ux?&&?x1?>=?root->dx?&&
            40???????y0?<=?root->uy?&&?y1?>=?root->dy)?{?//complete?cover
            41???????root->c?=?color;
            42???????return;
            43???}
            44???for?(int?i?=?0;i?<?4;i++)?{?//half?cover
            45???????if?(root->pt[i])?{
            46???????????/*?I?think?it?is?the?fatal?statement?which?is?used?to?expand?the?root?color
            47????????????*?to?the?desendants?*/
            48???????????if?(root->c?!=?NEG)?{????
            49???????????????root->pt[i]->c?=?root->c;
            50???????????}
            51???????????dye(root->pt[i]);
            52???????}
            53???}
            54???if?(root->c?!=?NEG)?{
            55???????root->c?=?NEG;
            56???}
            57?}
            58//http://www.shnenglu.com/schindlerlee/
            59?int?statics(node?*?root)
            60?{
            61???if?(root)?{
            62???????int?res?=?0;
            63???????if?(root->c?==?NEG)?{
            64???????????for?(int?i?=?0;i?<?4;i++)?{
            65???????????????res?+=?statics(root->pt[i]);
            66???????????}
            67???????}else?if?(root->c?==?0)?{
            68???????????res?=?(root->dy?-?root->uy?+?1)?*?(root->dx?-?root->ux?+?1);
            69???????}
            70???????return?res;
            71???}
            72???return?0;
            73?}
            74?
            75?int?main()
            76?{
            77???int?i,?j,?k,?ux,uy,dx,dy;
            78???char?c;
            79???scanf("%d%d",?&n,?&m);
            80???root?=?&pool[top++],?build(root,?1,?1,?n,?n);
            81???while?(m--)?{
            82???????scanf("%d?%d?%d?%d?%c",&ux,&uy,&dx,&dy,&c);
            83???????color?=?(c?==?'b');
            84???????x0?=?min(ux,dx),?x1?=?max(ux,dx);
            85???????y0?=?min(uy,dy),?y1?=?max(uy,dy);
            86???????dye(root);
            87???}
            88???printf("%d\n",statics(root));
            89???return?0;
            90?}
            91?
            92??

            posted on 2010-02-21 23:34 schindlerlee 閱讀(1685) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            亚洲AV日韩精品久久久久久久| 一级做a爰片久久毛片看看| 97精品依人久久久大香线蕉97 | 久久精品夜色噜噜亚洲A∨| 久久精品人妻一区二区三区| 亚洲国产成人久久笫一页| 7777精品久久久大香线蕉 | 99精品国产综合久久久久五月天| 无码伊人66久久大杳蕉网站谷歌| 久久国产精品-国产精品| 久久久久久久综合综合狠狠| 久久99热这里只频精品6| 精品久久久久久久无码| 亚洲Av无码国产情品久久| 91精品国产综合久久精品| 亚洲国产精品成人AV无码久久综合影院| 狠狠色丁香久久婷婷综合_中 | 久久天天日天天操综合伊人av| 亚洲AV日韩精品久久久久久久| 成人a毛片久久免费播放| 亚洲精品无码久久久影院相关影片 | 人妻精品久久久久中文字幕| 99久久精品国产麻豆| 欧美精品乱码99久久蜜桃| 国产午夜精品理论片久久| 久久综合狠狠综合久久综合88| 国产巨作麻豆欧美亚洲综合久久| 人妻精品久久无码专区精东影业| 青青草国产97免久久费观看| 久久精品国产一区二区三区不卡| 91精品国产高清久久久久久io | 精品久久久久一区二区三区 | 亚洲中文字幕无码久久2020| 思思久久好好热精品国产| 亚洲国产一成人久久精品| 亚洲日韩欧美一区久久久久我| 久久99久久成人免费播放| 成人精品一区二区久久| 91久久香蕉国产熟女线看| 色综合久久中文色婷婷| 久久免费线看线看|