题目链接
给出一个点，然后根据半径找到这个点左右区间。
计算出所有的区间，然后进行合并。
首先根据左区间增序排列，然后合并区间
如果后一个的左区间大于前一个的右区间，总数++，更新区间
如果后一个的右区间小于前一个的右区间，更新右区间
例如 【-9，-1】【-3，-3】【2，6】
区间更新分别为【-9，-1】，【-9，-3】【2，6】
#include<iostream> #include<algorithm> #include<map> #include<string> #include<vector> #include<cmath> using namespace std; typedef struct node{ double zuo,you; }node; node no[10000]; bool cmp(node n1,node n2){ return n1.zuo<n2.zuo; } int main(){ int n; double r; int cnt=0; while(scanf("%d %lf",&n,&r),n||r){ cnt++; int fz=0; for(int i=0;i<n;i++){ double a,b; cin>>a>>b; if(fz) continue; if(b>r){ fz=1; continue; } no[i].zuo=a-sqrt(r*r-b*b); no[i].you=a+sqrt(r*r-b*b); } if(fz){ printf("Case %d: -1\n",cnt); } else{ sort(no,no+n,cmp); int sum=1; //node temp=no[0]; double fz_zuo=no[0].zuo,fz_you=no[0].you; for(int i=1;i<n;i++){ //printf("%f %f\n",no[i].zuo,no[i].you); if(no[i].zuo>fz_you){ sum++;//cout<<"fz"<<" "<<i<<" "<<yo<<endl; fz_zuo=no[i].zuo; fz_you=no[i].you; } else if(no[i].you<fz_you) fz_you=no[i].you; } printf("Case %d: %d\n",cnt,sum); } } return 0; }