• <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>
            posts - 7,comments - 3,trackbacks - 0

             1043: Atlantis


            ResultTIME LimitMEMORY LimitRun TimesAC TimesJUDGE
            3s8192K431155Standard

            There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

            Input

            The input file consists of several test cases. Each test case starts with a line containing a single integer n(1 < n < 100) of available maps. The n following lines describe one map each. Each of these lines containsfour numbers x1;y1;x2;y2 (0 < x1 < x2 < 100000;0 < y1 < y2 < 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.The input file is terminated by a line containing a single 0. Don’t process it1.

            Output

            For each test case, your program should output one section. The first line of each section must be “Testcase #k”, where k is the number of the test case (starting with 1). The second one must be   “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.

            Output a blank line after each test case.

            Sample Input

            2
            10 10 20 20
            15 15 25 25.5
            0
            

            Sample Output

            Test case #1
            Total explored area: 180.00


            題目的意思是給定n個矩形的2n個坐標(biāo),求矩形的覆蓋面積。如果開一個大的bool數(shù)組,將覆蓋過的部分更新為true,再從頭到尾掃描一遍,在坐標(biāo)范圍比較小的情況下,可以求解。但是如果坐標(biāo)x,y的取值范圍很大,比如[-10^8,10^8],用上面這個方法就不能求解了;而且坐標(biāo)還有可能是實(shí)數(shù),上面的方法就更加不可行了,需要尋找一種新的解法,就是下面要說到的“離散化”。
                注意到要表示一個矩形,只需要知道其2個頂點(diǎn)的坐標(biāo)就可以了(最左下,最右上)??梢杂?個數(shù)組x[0...2n-1],y[0...2n-1]記錄下矩形Ri的2個坐標(biāo)(x1,y1),(x2,y2),然后將數(shù)組x[0...xn-1],y[0...2n-1]排序,為下一步的掃描線作準(zhǔn)備,這就是離散化的思想。這題還可以用線段樹做進(jìn)一步優(yōu)化,但是這里只介紹離散化的思想。
                看下面這個例子:有2個矩形(1,1),(3,3)和(2,2),(4,4)。如圖:
                圖中虛線表示掃描線,下一步工作只需要將這2個矩形覆蓋過的部分的bool數(shù)組的對應(yīng)位置更新為true,接下去用掃描線從左到右,從上到下掃描一遍,就可以求出矩形覆蓋的總面積。
                這個圖對應(yīng)的bool數(shù)組的值如下:
                1 1 0                       1 2 3
                1 1 1       <---->       4 5 6
                0 1 1                       7 8 9

            代碼:

            #include<stdio.h>
            #include
            <iostream>
            #include
            <algorithm>
            #define MAXN 201
            using namespace std;

            struct Node
            {
                
            int l, r;//線段樹的左右整點(diǎn)
                int c;//c用來記錄重疊情況
                double cnt, lf, rf;//
                
            //cnt用來計(jì)算實(shí)在的長度,rf,lf分別是對應(yīng)的左右真實(shí)的浮點(diǎn)數(shù)端點(diǎn)
            } segTree[MAXN * 3];
            struct Line
            {
                
            double x, y1, y2;
                
            int f;
            } line[MAXN];
            //把一段段平行于y軸的線段表示成數(shù)組 ,
            //x是線段的x坐標(biāo),y1,y2線段對應(yīng)的下端點(diǎn)和上端點(diǎn)的坐標(biāo)
            //一個矩形 ,左邊的那條邊f(xié)為1,右邊的為-1,
            //用來記錄重疊情況,可以根據(jù)這個來計(jì)算,nod節(jié)點(diǎn)中的c

            bool cmp(Line a,Line b)//sort排序的函數(shù)
            {
                
            return a.x < b.x;
            }

            double y[MAXN];//記錄y坐標(biāo)的數(shù)組
            void Build(int t,int l,int r)//構(gòu)造線段樹
            {
                segTree[t].l 
            = l;
                segTree[t].r 
            = r;
                segTree[t].cnt 
            = segTree[t].c = 0;
                segTree[t].lf 
            = y[l];
                segTree[t].rf 
            = y[r];
                
            if (l + 1 == r) return;
                
            int mid = (l + r) >> 1;
                Build(t 
            << 1, l, mid);
                Build(t 
            << 1 | 1, mid, r);//遞歸構(gòu)造
            }
            void calen(int t)//計(jì)算長度
            {
                
            if (segTree[t].c > 0)
                {
                    segTree[t].cnt 
            = segTree[t].rf - segTree[t].lf;
                    
            return;
                }
                
            if (segTree[t].l + 1 == segTree[t].r)
                    segTree[t].cnt 
            = 0;
                
            else
                    segTree[t].cnt 
            = segTree[t << 1].cnt + segTree[t << 1 | 1].cnt;
            }
            void update(int t, Line e)//加入線段e,后更新線段樹
            {
                
            if (e.y1 == segTree[t].lf && e.y2 == segTree[t].rf)
                {
                    segTree[t].c 
            += e.f;
                    calen(t);
                    
            return;
                }
                
            if (e.y2 <= segTree[t << 1].rf)
                    update(t 
            << 1, e);
                
            else
                
            if(e.y1 >= segTree[t << 1 | 1].lf)
                    update(t 
            << 1 | 1, e);
                
            else
                {
                    Line tmp 
            = e;
                    tmp.y2 
            = segTree[t << 1].rf;
                    update(t 
            << 1, tmp);
                    tmp 
            = e;
                    tmp.y1 
            = segTree[t << 1 | 1].lf;
                    update(t 
            << 1 | 1, tmp);
                }
                calen(t);
            }
            int main()
            {
                
            int i, n, t, iCase = 0;
                
            double x1, y1, x2, y2;
                
            while(scanf("%d"&n) && n)
                {
                    iCase
            ++;
                    t 
            = 1;
                    
            for(i = 1; i <= n; i++)
                    {
                        scanf(
            "%lf%lf%lf%lf"&x1, &y1, &x2, &y2);
                        line[t].x 
            = x1;
                        line[t].y1 
            = y1;
                        line[t].y2 
            = y2;
                        line[t].f 
            = 1;
                        y[t] 
            = y1;
                        t
            ++;
                        line[t].x 
            = x2;
                        line[t].y1 
            = y1;
                        line[t].y2 
            = y2;
                        line[t].f 
            = -1;
                        y[t] 
            = y2;
                        t
            ++;
                    }
                    sort(line 
            + 1, line + t, cmp);
                    sort(y 
            + 1, y + t);
                    Build(
            11, t - 1);
                    update(
            1, line[1]);
                    
            double res = 0;
                    
            for(i = 2; i < t; i++)
                    {
                        res 
            += segTree[1].cnt * (line[i].x - line[i - 1].x);
                        update(
            1, line[i]);
                    }
                    printf(
            "Test case #%d\n", iCase);
                    printf(
            "Total explored area: %.2lf\n\n", res);
                }
                
            return 0;
            }
            posted on 2011-10-25 23:52 LLawliet 閱讀(257) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            亚洲级αV无码毛片久久精品| 亚洲色婷婷综合久久| 国产精品一区二区久久精品| 国产精品美女久久久久久2018| 久久夜色精品国产亚洲| 久久久久久综合一区中文字幕 | 国产一级做a爰片久久毛片| 国产精品一久久香蕉国产线看| 国产伊人久久| 无码人妻久久久一区二区三区| 久久久精品午夜免费不卡| 一本一道久久a久久精品综合 | 一本大道久久a久久精品综合| 亚洲AⅤ优女AV综合久久久| 国产精品美女久久久久| 亚洲国产高清精品线久久| 久久66热人妻偷产精品9| 色婷婷综合久久久久中文字幕| 69久久精品无码一区二区| 久久国产AVJUST麻豆| 99久久精品免费国产大片| 亚洲伊人久久精品影院| 青春久久| 青青草原综合久久大伊人导航| 久久久久中文字幕| 亚洲va久久久噜噜噜久久 | 99久久精品久久久久久清纯| 久久久久女人精品毛片| 怡红院日本一道日本久久| 久久久国产精品亚洲一区| 久久久精品波多野结衣| 亚洲午夜精品久久久久久人妖| 日日躁夜夜躁狠狠久久AV| 偷窥少妇久久久久久久久| 久久www免费人成看国产片| 欧美久久精品一级c片片| 91精品国产高清久久久久久io | 国产综合精品久久亚洲| 久久精品免费观看| 久久青青草原国产精品免费| 狠狠色丁香久久综合五月|