对于x轴上方的每个建筑 可以计算出x轴上一段区间可以包含这个点 所以就转化成 有多少个区间可以涵盖这所有的点
排序之后贪心一下就ok
用cin 好像一直t看了好多blog 改了scanf 过了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<cmath> using namespace std; ; int n,c[maxn]; struct ac{ double x,y; }a[maxn]; bool cmp(ac q,ac w){ return q.x<w.x; } int main(){ ; double d; bool fa; cin>>n>>d; ||d!=){ fa=; ;j<=n;j++){ double x,y; scanf("%lf%lf",&x,&y); ; else{ a[j].x=x*1.0-sqrt(d * d - y * y); a[j].y=x*1.0+sqrt(d * d - y * y); } } ; ) printf("Case %d: -1\n",tot++); else{ sort(a+,a++n,cmp); ac aa=a[]; ;j<=n;j++){ if(a[j].x>aa.y){ ans++; aa=a[j]; }else if(a[j].y<aa.y){ aa=a[j]; } } printf("Case %d: %d\n",tot++,ans); } cin>>n>>d; } ; }