總算過了這個題了。。。。。。
教訓：
1。對于qsort的cmp函數的寫法要養成好習慣，最好要這么寫：
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 > 0) return 1;
10 if (pp < 0) return -1;
11 }
12 }
否則，如果直接return
(*(point *)a).s -(*(point *)b).s;的話，對于一般的int型沒什么問題，但是對于浮點數就會出現精度問題了，比如return -0.3就會變成return 0
2。區間合并的時候要注意上限要不斷調整。。。
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 *c = (point *)a;
17 point *d = (point *)b;
18 if(c->s != d->s)
19 return c->s - d->s;
20 else
21 return c->e - d->e;
22 }
23
24 inline double dist(point a)
25 {
26 return sqrt( d*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; //就是這里了，錯在沒有對其它的情況更新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 > 0) return 1;
22 if (pp < 0) return -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>d || noans == 1)
59 {
60 noans = 1;
61 }
62 else
63 {
64 double l = sqrt( (double)(d*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 閱讀(1310)
評論(1) 編輯 收藏 引用 所屬分類:
Problem Solving