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

            pku 1262 input 離散化

            題意:
            給出一些瓷磚,以及需要鋪的面積w*h(從(0,0)到(w,h)),求:
            (1)這些瓷磚是否有重疊
            (2)這些瓷磚是否超過了地面的邊界
            (3)這些瓷磚能否完整的鋪蓋地面
            瓷磚個數n<100
            解法:
            對于第一問,傳統的做法應該是離散化+線段樹。但是此題數據量很小,n<100離散化后面積不過160000,可以暴力判重。
            對于第二問,掃描一遍即可
            對于第三問,計算下總面積即可。
            代碼:
             1 # include <cstdio>
             2 using namespace std;
             3 # include <vector>
             4 # include <algorithm>
             5 # include <cstring>
             6 int data[101][4],c1,tmp1[500],c2,tmp2[500],n,w,h;
             7 bool used[500][500];
             8 int main()
             9 {
            10     int test;
            11     scanf("%d",&test);
            12     while(test--)
            13     {
            14         int total=0;
            15         scanf("%d%d%d",&w,&h,&n);
            16         c1=c2=0;
            17         memset(used,0,sizeof(used));
            18         for(int i=0;i<n;i++)
            19         {
            20             scanf("%d%d%d%d",&data[i][0],&data[i][1],&data[i][2],&data[i][3]);
            21             tmp1[c1++]=data[i][0];
            22             tmp1[c1++]=data[i][2]-1;
            23             tmp2[c2++]=data[i][1];
            24             tmp2[c2++]=data[i][3]-1;
            25         }
            26         sort(tmp1,tmp1+c1);
            27         c1=unique(tmp1,tmp1+c1)-tmp1;
            28         sort(tmp2,tmp2+c2);
            29         c2=unique(tmp2,tmp2+c2)-tmp2;
            30         for(int i=0;i<n;i++)
            31         {
            32             int xl=lower_bound(tmp1,tmp1+c1,data[i][0])-tmp1,xh=lower_bound(tmp1,tmp1+c1,data[i][2]-1)-tmp1;
            33             int yl=lower_bound(tmp2,tmp2+c2,data[i][1])-tmp2,yh=lower_bound(tmp2,tmp2+c2,data[i][3]-1)-tmp2;
            34             for(int j=xl;j<=xh;j++)
            35                 for(int k=yl;k<=yh;k++)
            36                     if(used[j][k])
            37                     {
            38                         printf("NONDISJOINT\n");
            39                         goto end;
            40                     }
            41                     else used[j][k]=true;
            42         }
            43         for(int i=0;i<n;i++)
            44             if(data[i][0]<0||data[i][0]>w||data[i][2]<0||data[i][2]>w||data[i][1]<0||data[i][1]>h||data[i][3]<0||data[i][3]>h)
            45             {
            46                 printf("NONCONTAINED\n");
            47                 goto end;
            48             }
            49         for(int i=0;i<n;i++)
            50             total+=(data[i][2]-data[i][0])*(data[i][3]-data[i][1]);
            51         if(total!=w*h) printf("NONCOVERING\n");
            52         else printf("OK\n");
            53         end:;
            54     }
            55 }
            56 

            posted on 2010-12-10 16:52 yzhw 閱讀(156) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            亚洲国产成人久久笫一页 | 久久天天日天天操综合伊人av| 国产精品女同久久久久电影院 | 久久精品国产精品亚洲毛片| 久久超乳爆乳中文字幕| 韩国三级中文字幕hd久久精品 | 狠狠综合久久综合88亚洲| 久久国产劲爆AV内射—百度| 九九精品99久久久香蕉| 成人精品一区二区久久| 区久久AAA片69亚洲| 亚洲天堂久久精品| 久久综合国产乱子伦精品免费| 99久久精品国产一区二区蜜芽| 精品国产99久久久久久麻豆| 国内精品久久久久影院日本| 久久久久亚洲AV成人网人人网站| 日韩av无码久久精品免费| 亚洲国产一成久久精品国产成人综合 | 无码人妻精品一区二区三区久久 | 欧美麻豆久久久久久中文| 久久人人爽人人爽人人AV东京热 | 99久久国产免费福利| 久久久久久久97| 欧美激情精品久久久久久久九九九| 久久久久久久人妻无码中文字幕爆 | 久久综合欧美成人| 久久亚洲AV成人无码国产 | 亚洲欧美一区二区三区久久| 久久电影网2021| 久久精品国产99久久久| 久久久久se色偷偷亚洲精品av| 精品久久久久久无码中文野结衣| 99久久国产综合精品麻豆| 欧美牲交A欧牲交aⅴ久久| 久久国产劲爆AV内射—百度| 精品久久久中文字幕人妻| 久久久久亚洲AV无码观看| 国产成人综合久久精品红| 综合久久给合久久狠狠狠97色| 久久天天躁狠狠躁夜夜av浪潮|