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

            POJ 1151 Atlantis 離散化+掃描線

            Problem Description
            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 contains four 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 it.
             

            Output
            For each test case, your program should output one section. The first line of each section must be “Test case #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個坐標,求矩形的覆蓋面積。如果開一個大的bool數組,將覆蓋過的部分更新為true,再從頭到尾掃描一遍,在坐標范圍比較小的情況下,可以求解。但是如果坐標x,y的取值范圍很大,比如[-10^8,10^8],用上面這個方法就不能求解了;而且坐標還有可能是實數,上面的方法就更加不可行了,需要尋找一種新的解法,就是下面要說到的“離散化”。
                注意到要表示一個矩形,只需要知道其2個頂點的坐標就可以了(最左下,最右上)??梢杂?個數組x[0...2n-1],y[0...2n-1]記錄下矩形Ri的2個坐標(x1,y1),(x2,y2),然后將數組x[0...xn-1],y[0...2n-1]排序,為下一步的掃描線作準備,這就是離散化的思想。這題還可以用線段樹做進一步優化,但是這里只介紹離散化的思想。
                看下面這個例子:有2個矩形(1,1),(3,3)和(2,2),(4,4)。如圖:
                圖中虛線表示掃描線,下一步工作只需要將這2個矩形覆蓋過的部分的bool數組的對應位置更新為true,接下去用掃描線從左到右,從上到下掃描一遍,就可以求出矩形覆蓋的總面積。
                這個圖對應的bool數組的值如下:
                1 1 0                       1 2 3
                1 1 1       <---->       4 5 6
                0 1 1                       7 8 9
             1 #include <iostream>
             2 #include <cmath>
             3 using namespace std;
             4 
             5 const int N = 101;
             6 const double eps = 1e-6;
             7 double ans,x[2*N],y[2*N];
             8 double pos[N][4];
             9 bool hash[2*N][2*N];
            10 
            11 int cmp(const void *a,const  void *b){
            12     double *aa = (double *)a;
            13     double *bb = (double *)b;
            14     if(fabs(*aa-*bb)<=eps) return 0;
            15     else if(*aa-*bb>0return 1;
            16     else return -1;
            17 }
            18 int main(){
            19     int i,j,k,n,x1,x2,y1,y2,ca=1;
            20     while(scanf("%d",&n),n){
            21         for(ans=i=k=0;i<n;i++,k+=2){
            22             scanf("%lf %lf %lf %lf",&pos[i][0],&pos[i][1],&pos[i][2],&pos[i][3]);
            23             x[k]=pos[i][0],y[k]=pos[i][1],x[k+1]=pos[i][2],y[k+1]=pos[i][3];
            24         }
            25         memset(hash,false,sizeof(hash));
            26         qsort(x,2*n,sizeof(x[0]),cmp);
            27         qsort(y,2*n,sizeof(y[0]),cmp);
            28         for(i=0;i<n;i++){
            29             for(k=0;fabs(x[k]-pos[i][0])>eps;k++); x1=k;
            30             for(k=0;fabs(y[k]-pos[i][1])>eps;k++); y1=k;
            31             for(k=0;fabs(x[k]-pos[i][2])>eps;k++); x2=k;
            32             for(k=0;fabs(y[k]-pos[i][3])>eps;k++); y2=k;
            33             for(j=x1;j<x2;j++for(k=y1;k<y2;k++)
            34                 hash[j][k]=true;
            35         }
            36         for(i=0;i<2*n-1;i++)
            37             for(j=0;j<2*n-1;j++)
            38                 ans+=hash[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);            
            39         printf("Test case #%d\n",ca++);
            40         printf("Total explored area: %.2lf\n",ans);
            41         printf("\n");
            42     }
            43     return 0;
            44 }

            posted on 2009-04-26 19:43 極限定律 閱讀(725) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年4月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            精品久久久久成人码免费动漫 | 18禁黄久久久AAA片| 青青草国产精品久久| 久久国产精品免费一区二区三区| 国产精品99久久精品| 久久久久高潮综合影院| 久久精品国产亚洲AV无码娇色 | 91精品国产综合久久精品| 漂亮人妻被黑人久久精品| 女人香蕉久久**毛片精品| 亚洲国产精品综合久久网络 | 狠狠色狠狠色综合久久| 人妻少妇久久中文字幕| 人妻无码精品久久亚瑟影视| 免费精品国产日韩热久久| 97久久久久人妻精品专区| 国产亚洲美女精品久久久2020| 99久久精品免费看国产一区二区三区| 国产精品久久久久无码av| 久久婷婷五月综合97色直播| 国内精品久久久久伊人av| 久久综合视频网| 性欧美大战久久久久久久久| 久久人人爽人人人人片av| 亚洲国产精品18久久久久久| 久久伊人五月丁香狠狠色| 综合久久精品色| 久久久久久夜精品精品免费啦 | 久久99中文字幕久久| 久久国产精品久久| 日本精品久久久久影院日本| 亚洲欧美日韩精品久久亚洲区| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 久久婷婷综合中文字幕| 久久免费99精品国产自在现线| 欧美日韩精品久久久久| www久久久天天com| 久久精品国产精品青草app| 久久精品国产第一区二区| 日韩精品久久久久久久电影| 丁香久久婷婷国产午夜视频|