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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 3168 Barn Expansion 快排

            思路:

            一開始想到用線段樹來做,但是發現坐標范圍異常的大,放一個都勉勉強強,更不用說幾個了!
            想了一下,發現有一個至關重要的條件“不存在覆蓋的情況”。
            那就沒必要用線段樹了,因為壓根就沒必要解決覆蓋問題。
            可以用一種取巧的方法解決這題。



            對于每個矩形,首先把它 y 方向的兩條邊抽取出來。
            對于所有矩形的 y 方向的邊,先按照 x 排序,然后按照頂端的 y 坐標排序。



            然后對于位于同一 x 坐標的邊,找出所有首尾相接或者有交集的邊。
            那么這些邊對應的矩形必定要排除。

            對于 x 方向的邊,作同樣的處理。

            排除完之后,剩下的矩形就是可以答案了。

            代碼 500 多ms。。
            #include <stdio.h>
            #include 
            <stdlib.h>

            #define MAX_N 25032

            struct node {
                
            int barn, start, end, idx;
            }
            ;
            struct node vert[MAX_N * 2], hori[MAX_N * 2];
            char cannot[MAX_N];
            int N, ans;

            __inline 
            void add_node(struct node *t, int barn, int start, int end, int idx)
            {
                t
            ->barn = barn;
                t
            ->start = start;
                t
            ->end = end;
                t
            ->idx = idx;
            }


            int cmp_node(const void *a, const void *b)
            {
                
            struct node *p, *q;
                p 
            = (struct node *)a;
                q 
            = (struct node *)b;
                
            if (p->idx != q->idx)
                    
            return p->idx - q->idx;
                
            return p->start - q->start;
            }


            __inline 
            void disable_barn(int barn)
            {
                
            if (!cannot[barn]) {
                    cannot[barn] 
            = 1;
                    ans
            --;
                }
             
            }


            __inline 
            void calc(struct node *arr, int len)
            {
                
            int i, idx, end, cnt, first;

                i 
            = 0;
                
            while (i < len) {
                    idx 
            = arr[i].idx;
                    end 
            = arr[i].end;
                    first 
            = i;
                    cnt 
            = 0;
                    i
            ++;
                    
            while (i < len && arr[i].idx == idx && arr[i].start <= end) {
                        
            if (arr[i].end > end)
                            end 
            = arr[i].end;
                        disable_barn(arr[i].barn);
                        cnt
            ++;
                        i
            ++;
                    }

                    
            if (cnt)
                        disable_barn(arr[first].barn);
                }

            }


            int main()
            {
                
            int i, top, left, bottom, right;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d"&N);
                ans 
            = N;
                
            for (i = 0; i < N; i++{
                    scanf(
            "%d%d%d%d"&left, &bottom, &right, &top);
                    add_node(
            &vert[i * 2], i, bottom, top, left);
                    add_node(
            &vert[i * 2 + 1], i, bottom, top, right);
                    add_node(
            &hori[i * 2], i, left, right, top);
                    add_node(
            &hori[i * 2 + 1], i, left, right, bottom);
                }

                qsort(vert, N 
            * 2sizeof(vert[0]), cmp_node);
                qsort(hori, N 
            * 2sizeof(hori[0]), cmp_node);
                calc(vert, N 
            * 2);
                calc(hori, N 
            * 2);
                printf(
            "%d\n", ans);

                
            return 0;
            }


            posted on 2010-03-18 15:52 糯米 閱讀(647) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            久久精品国产福利国产琪琪| 久久国产精品一国产精品金尊| 99久久99久久精品国产片果冻| 99久久免费国产精品| 99久久这里只有精品| 国产V综合V亚洲欧美久久| 99久久99久久| 精品久久久久久成人AV| 久久精品国产亚洲AV无码麻豆| 久久人人爽爽爽人久久久| 久久国产精品-久久精品| 99久久精品这里只有精品| 一本久久a久久精品综合夜夜| 青草影院天堂男人久久| 亚洲午夜无码久久久久小说| 久久无码中文字幕东京热| 久久久无码精品亚洲日韩蜜臀浪潮| 久久国产劲爆AV内射—百度| 久久精品国产精品青草app| 99久久精品午夜一区二区| 久久91精品久久91综合| 国产精品无码久久久久| 亚洲精品国产美女久久久| 久久国产免费直播| 亚洲AV伊人久久青青草原| 精品国产VA久久久久久久冰| 精品久久一区二区| 少妇久久久久久被弄到高潮| 久久精品国产99久久久古代| 伊人久久大香线焦综合四虎| 日本精品久久久久影院日本| 欧美精品久久久久久久自慰| 久久99热国产这有精品| 久久精品无码一区二区三区免费| 久久久国产视频| 青青草国产精品久久| 香蕉久久夜色精品国产2020| 亚洲AV日韩AV永久无码久久| 久久久久久一区国产精品| 亚洲国产另类久久久精品小说| 99久久伊人精品综合观看|