• <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 閱讀(1684) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            国产成人精品久久一区二区三区av| 久久影视综合亚洲| 亚洲AV日韩精品久久久久| 久久综合给合久久狠狠狠97色| 久久亚洲精品国产精品| 久久91精品久久91综合| 国内精品久久久久久不卡影院| 久久亚洲中文字幕精品一区四| 伊人久久大香线蕉综合Av| 国产精品99久久精品| 色婷婷狠狠久久综合五月| 伊人色综合久久天天人手人婷 | 精品无码久久久久国产| 国产精品女同一区二区久久| 亚洲午夜久久久影院伊人| 国产精品久久久久久久午夜片| 久久精品国产亚洲AV忘忧草18| 成人精品一区二区久久 | 久久午夜无码鲁丝片| 国产伊人久久| 色综合久久综精品| 精品亚洲综合久久中文字幕| 99久久综合国产精品免费| 久久久精品人妻无码专区不卡 | 国产精品99久久久久久www| 无码人妻久久一区二区三区| 久久综合久久伊人| 91久久福利国产成人精品| 99久久国语露脸精品国产| 99久久99久久精品国产片果冻| 伊人精品久久久久7777| 26uuu久久五月天| 91亚洲国产成人久久精品网址| 99久久精品国产麻豆| 久久精品国产亚洲AV无码娇色| 中文字幕久久精品无码| 色综合久久无码中文字幕| 色综合久久久久无码专区 | 久久天天躁狠狠躁夜夜躁2O2O| 国产精品久久久久蜜芽| 精品久久久久成人码免费动漫 |