• <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浪潮| 亚洲一区二区三区日本久久九| 丰满少妇人妻久久久久久4| 色偷偷91久久综合噜噜噜噜| 中文字幕无码精品亚洲资源网久久| 日韩人妻无码一区二区三区久久| A狠狠久久蜜臀婷色中文网| 久久久久这里只有精品| 婷婷久久久亚洲欧洲日产国码AV | 久久久久久精品免费免费自慰| 亚洲国产精品一区二区久久hs| 91久久国产视频| 亚洲AV无码久久精品色欲| 国产三级观看久久| 精品久久久久久国产潘金莲| 久久久久国色AV免费看图片 | 久久香蕉一级毛片| 久久久久久久精品成人热色戒 | 精品久久香蕉国产线看观看亚洲| 久久人妻少妇嫩草AV蜜桃| 成人国内精品久久久久影院| 中文字幕久久亚洲一区| 狠狠色综合网站久久久久久久| 久久亚洲欧美国产精品| 亚洲综合伊人久久综合| 中文字幕精品无码久久久久久3D日动漫| 久久国产免费观看精品| 国产69精品久久久久777| 午夜人妻久久久久久久久| 久久亚洲精品无码aⅴ大香| 久久亚洲国产成人影院网站| 青青青伊人色综合久久| 91久久精品91久久性色| 97久久精品人妻人人搡人人玩| 人妻少妇久久中文字幕| 亚洲午夜无码久久久久| 久久香蕉国产线看观看精品yw| 日韩人妻无码一区二区三区久久| 久久精品国产清自在天天线|