• <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)這些瓷磚能否完整的鋪蓋地面
            瓷磚個(gè)數(shù)n<100
            解法:
            對(duì)于第一問,傳統(tǒng)的做法應(yīng)該是離散化+線段樹。但是此題數(shù)據(jù)量很小,n<100離散化后面積不過160000,可以暴力判重。
            對(duì)于第二問,掃描一遍即可
            對(duì)于第三問,計(jì)算下總面積即可。
            代碼:
             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 閱讀(155) 評(píng)論(0)  編輯 收藏 引用 所屬分類: data struct

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

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            統(tǒng)計(jì)系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            亚洲а∨天堂久久精品| 久久久精品国产Sm最大网站| 欧美亚洲国产精品久久高清| 欧美一区二区精品久久| 99久久婷婷国产一区二区| 99久久免费只有精品国产| 日本加勒比久久精品| 精品久久久无码人妻中文字幕| 色8久久人人97超碰香蕉987| 91精品国产高清久久久久久io | 色噜噜狠狠先锋影音久久| 国产91色综合久久免费分享| 久久美女网站免费| 少妇内射兰兰久久| 2021国产成人精品久久| 99久久夜色精品国产网站 | 久久影视综合亚洲| 香港aa三级久久三级老师2021国产三级精品三级在| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 久久精品国产亚洲av影院| 久久精品国产网红主播| 久久午夜伦鲁片免费无码| 狠狠色综合久久久久尤物| 国产精品久久久久久福利漫画| 亚洲精品无码久久久久AV麻豆| 久久免费美女视频| 色婷婷综合久久久久中文一区二区| 久久人人爽人人爽AV片| 久久99精品久久久久子伦| 精品一二三区久久aaa片| 婷婷久久综合九色综合九七| 国产精品久久久久影院嫩草| 一本一本久久A久久综合精品 | 国产成人无码精品久久久性色| 久久综合日本熟妇| 久久电影网2021| 国产成人精品久久免费动漫| 亚洲精品无码久久久久| 久久人妻少妇嫩草AV无码专区| 欧美黑人又粗又大久久久| 久久亚洲AV成人无码|