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


            May the force be with you!
            posts - 52,  comments - 33,  trackbacks - 0
            總算過了這個(gè)題了。。。。。。
            教訓(xùn):
                1。對(duì)于qsort的cmp函數(shù)的寫法要養(yǎng)成好習(xí)慣,最好要這么寫:
                  
             1 int cmp ( const void * a, const void * b)
             2 {
             3     double ss = (*(point *)a).s -(*(point *)b).s;
             4     if (ss > 0 ) return 1;
             5     if (ss < 0 ) return -1;
             6     if (ss==0)
             7     {
             8         double pp=(*(point *)a).e -(*(point *)b).e;
             9         if (pp > 0return 1;
            10         if (pp < 0return -1;
            11     }
            12 }

                否則,如果直接return (*(point *)a).s -(*(point *)b).s;的話,對(duì)于一般的int型沒什么問題,但是對(duì)于浮點(diǎn)數(shù)就會(huì)出現(xiàn)精度問題了,比如return -0.3就會(huì)變成return 0
               
                2。區(qū)間合并的時(shí)候要注意上限要不斷調(diào)整。。。

                                                                               simbaforrest
                                                                               2007/12/27
            以下是Wrong Answer代碼
             1 #include <stdio.h>
             2 #include <stdlib.h>
             3 #include <string.h>
             4 #include <math.h>
             5 const int maxn = 1010;
             6 int n,d,ans;
             7 typedef struct
             8 {
             9     int x,y;
            10     double s,e;
            11 }point;
            12 point island[maxn];
            13 
            14 int cmp(const void *a, const void *b)
            15 {
            16     point *= (point *)a;
            17     point *= (point *)b;
            18     if(c->!= d->s)
            19         return c->- d->s;
            20     else
            21         return c->- d->e;
            22 }
            23 
            24 inline double dist(point a)
            25 {
            26     return sqrt( d*- a.y*a.y );
            27 }
            28 
            29 void solve()
            30 {
            31     for(int i=0; i<n; i++)
            32     {
            33         double l = dist(island[i]);
            34         island[i].s = (island[i].x - l);
            35         island[i].e = (island[i].x + l);
            36         
            37     }
            38     qsort(island,n,sizeof(point),cmp);
            39     
            40     ans = 1;
            41     double uplimit = island[0].e;
            42     for(int i=1; i<n; i++)
            43     {
            44         //printf("x=%d , y=%d\n",island[i].x,island[i].y);
            45         //printf("s=%lf , e=%lf\n",island[i].s,island[i].e);
            46         if(island[i].s - uplimit > 1e-3)
            47         {
            48             ans++;
            49             uplimit = island[i].e;      //就是這里了,錯(cuò)在沒有對(duì)其它的情況更新uplimit
            50         }
            51     }
            52 }
            53 
            54 int main()
            55 {
            56     int t=1;
            57     while(scanf("%d%d",&n,&d),n&&d)
            58     {
            59         bool noans = 0;
            60         for(int i=0; i<n; i++)
            61         {
            62             scanf("%d%d",&island[i].x,&island[i].y);
            63             if(island[i].y>d)
            64                 noans = 1;
            65         }
            66         if(!noans)
            67             solve();
            68         else
            69             ans = -1;
            70         printf("Case %d: %d\n",t++,ans);
            71     }
            72     return 0;
            73 }
            74 

            以下是AC代碼
             1 #include <stdio.h>
             2 #include <stdlib.h>
             3 #include <string.h>
             4 #include <math.h>
             5 typedef struct
             6 {
             7   double s,e;
             8 }point;
             9 point island[1010];
            10 int n,d,ans;
            11 double me;
            12 
            13 int cmp ( const void * a, const void * b)
            14 {
            15     double ss = (*(point *)a).s -(*(point *)b).s;
            16   if (ss > 0 ) return 1;
            17     if (ss < 0 ) return -1;
            18     if (ss==0)
            19   {
            20         double pp=(*(point *)a).e -(*(point *)b).e;
            21         if (pp > 0return 1;
            22         if (pp < 0return -1;
            23     }
            24 }
            25 
            26 void solve()
            27 {
            28   qsort(island,n,sizeof(island[0]),cmp);
            29   ans = 1;
            30   me = island[0].e;
            31   for(int i=1; i<n; i++)
            32   {
            33     if(island[i].s > me)
            34     {
            35       me = island[i].e;
            36       ans++;
            37     }
            38     else
            39     {
            40       if(island[i].e < me)
            41       {
            42         me = island[i].e;
            43       }
            44     }
            45   }
            46 }
            47 
            48 int main()
            49 {
            50   int t=1;
            51   while(scanf("%d%d",&n,&d),(n!=0)||(d!=0))
            52   {
            53     bool noans = 0;
            54     for(int i=0; i<n; i++)
            55     {
            56       int x,y;
            57       scanf("%d%d",&x,&y);
            58       if(y>|| noans == 1)
            59       {
            60         noans = 1;
            61       }
            62       else
            63       {
            64         double l = sqrt( (double)(d*- y*y) );
            65         island[i].s = (double)x-l;
            66         island[i].e = (double)x+l;
            67       }
            68     }
            69     if(noans==1)
            70     {
            71       ans = -1;
            72       printf("Case %d: %d\n",t++,ans);
            73     }
            74     else
            75     {
            76       solve();
            77       printf("Case %d: %d\n",t++,ans);
            78     }
            79   }
            80   return 0;
            81 }
            82 


            posted on 2007-12-27 15:16 R2 閱讀(1305) 評(píng)論(1)  編輯 收藏 引用 所屬分類: Problem Solving

            FeedBack:
            # re: ACM@PKU——1328(貪心+排序)
            2007-12-27 17:50 | winsty
            為什么不用STL的sort?  回復(fù)  更多評(píng)論
              
            你是第 free hit counter 位訪客




            <2025年8月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(4)

            隨筆分類(54)

            隨筆檔案(52)

            文章檔案(1)

            ACM/ICPC

            技術(shù)綜合

            最新隨筆

            搜索

            •  

            積分與排名

            • 積分 - 64180
            • 排名 - 357

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            精品综合久久久久久97超人| 亚洲国产精品成人AV无码久久综合影院| 国产欧美久久久精品影院| 久久国内免费视频| 97久久久精品综合88久久| 久久精品综合一区二区三区| 久久婷婷成人综合色综合| 久久99久久成人免费播放| 人妻久久久一区二区三区| 久久精品国产亚洲一区二区三区| 大香伊人久久精品一区二区| 亚洲嫩草影院久久精品| 无码精品久久久久久人妻中字| 久久精品一区二区三区中文字幕| 久久久久国产精品熟女影院| 久久精品成人免费观看97| 91精品国产色综合久久| 久久精品中文字幕无码绿巨人| 久久综合久久性久99毛片| 亚洲国产精品久久久久婷婷软件| 亚洲国产精品无码久久一区二区| 99久久精品国产毛片| 久久国产欧美日韩精品| 中文字幕久久久久人妻| 亚洲人成网站999久久久综合| www亚洲欲色成人久久精品| 97久久综合精品久久久综合| 性做久久久久久久| 中文字幕热久久久久久久| 婷婷综合久久中文字幕蜜桃三电影| 久久久亚洲裙底偷窥综合| 久久人人爽人人爽人人片AV麻烦| 久久精品国产一区二区三区| 精品久久综合1区2区3区激情| 国产美女久久久| 亚洲精品高清久久| 久久精品免费大片国产大片| 亚洲伊人久久成综合人影院 | 亚洲国产天堂久久综合| 久久精品亚洲精品国产欧美| 久久99国产精品成人欧美|