• <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 糯米 閱讀(646) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            精品久久亚洲中文无码| 综合久久国产九一剧情麻豆| 无码精品久久一区二区三区| 香蕉久久夜色精品升级完成| 亚洲午夜久久久| 亚洲国产成人久久综合区| 一本久道久久综合狠狠躁AV| 色成年激情久久综合| 亚洲AV日韩精品久久久久| 国产精品99久久久久久董美香 | 日产精品久久久久久久| 夜夜亚洲天天久久| 国内精品久久人妻互换| 伊人久久一区二区三区无码| 久久人人爽人人爽人人片AV东京热 | 伊人久久久AV老熟妇色| 久久精品国产乱子伦| 狠狠88综合久久久久综合网| 99国产精品久久久久久久成人热| 东京热TOKYO综合久久精品 | 久久影院亚洲一区| 亚洲国产精品18久久久久久| 久久国产精品无码HDAV| 色诱久久久久综合网ywww | 色欲久久久天天天综合网精品| 中文字幕久久欲求不满| 精品国产VA久久久久久久冰| 99国产欧美久久久精品蜜芽| 久久最新精品国产| 久久综合精品国产一区二区三区| 亚洲国产精品综合久久网络| 人妻久久久一区二区三区| 国产成人久久久精品二区三区| 久久综合偷偷噜噜噜色| 国产69精品久久久久777| 青青热久久国产久精品| 日本人妻丰满熟妇久久久久久| 久久精品国产亚洲7777| 国产亚洲精久久久久久无码| 一级A毛片免费观看久久精品| 97久久超碰国产精品2021|