題目鏈接：http://acm.nyist.net/JudgeOnline/problem.php?pid=287

解題思路：首先求出來每個點的臨界區(qū)域，即這個圓心能夠?qū)⑵涓采w的范圍。。。求出了每個點的覆蓋區(qū)域，那么問題就轉(zhuǎn)化為區(qū)間的覆蓋問題了。。。在算重疊的部分花了好長的時間而且還沒有寫好，還是沒有把出現(xiàn)的情況討論清楚。。。

AC:

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std;struct node {double left,right; }a[1005]; bool cmp(node a,node b) {return a.left < b.left; }int main() {int n,d,cas = 1;bool flag;while(scanf("%d%d",&n,&d)!=EOF && n + d){flag = false;for(int i = 0; i < n; i++){int x,y;scanf("%d%d",&x,&y);double tmp = double(d*d - y*y);if(tmp >= 0){tmp = sqrt(tmp);a[i].left = x - tmp;a[i].right = x + tmp;}else flag = true;}if(flag){printf("Case %d: -1\n",cas++);continue;}sort(a,a+n,cmp);int cnt = 1;double t = a[0].right;for(int i = 1; i < n; i++){if(a[i].left > t){cnt++;t = a[i].right;}else{if(a[i].right < t)t = a[i].right;}}printf("Case %d: %d\n",cas++,cnt);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的nyoj 287(区间覆盖)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。