• <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
            數(shù)據加載中……

            POJ 3168 Barn Expansion 快排

            思路:

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



            對于每個矩形,首先把它 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

            久久影院久久香蕉国产线看观看| 青春久久| 久久精品国产福利国产秒| 久久精品视频免费| 亚洲国产精品久久久久网站| 思思久久精品在热线热| 中文字幕成人精品久久不卡| 国产亚州精品女人久久久久久 | 久久福利片| 国产精品久久久久久五月尺| 亚洲AV无码久久| 日韩久久无码免费毛片软件| 久久精品国产亚洲AV久| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 久久精品成人免费国产片小草 | 久久国产综合精品五月天| 亚洲va久久久噜噜噜久久| 国产成人久久777777| 99久久精品国产一区二区蜜芽| 一级做a爰片久久毛片看看| 久久久久久久综合日本亚洲| 99久久精品国产高清一区二区| 亚洲人成伊人成综合网久久久| 一级a性色生活片久久无少妇一级婬片免费放 | 漂亮人妻被中出中文字幕久久| 国产精品视频久久| 亚洲精品无码成人片久久| 日韩欧美亚洲综合久久影院Ds| 久久亚洲高清观看| 久久精品无码专区免费青青| 粉嫩小泬无遮挡久久久久久| www.久久热.com| 无码精品久久久天天影视| 波多野结衣久久精品| 亚洲天堂久久久| 久久亚洲日韩精品一区二区三区| 亚洲精品国产美女久久久| 亚洲国产一成久久精品国产成人综合| 色综合久久最新中文字幕| 人人狠狠综合久久亚洲88| 国产午夜福利精品久久|