4 条题解
- 
  0
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1010; int n,d; struct Segment { double l,r; bool operator < (const Segment& t) const { return r<t.r; } }seg[N]; int main() { cin>>n>>d; bool failed=false; for(int i=0;i<n;i++) { int x,y; cin>>x>>y; //将平面问题转化到横轴上的一个个区间 if(y>d) failed=true; //如果比半径大,直接fail else { double len=sqrt(d*d-y*y); seg[i].l=x-len,seg[i].r=x+len; //区间左端点l,区间右端点r } } if(failed) puts("-1"); else { sort(seg,seg+n); int cnt=0; double last=-1e20; //last表示上一个区间的右端点 for(int i=0;i<n;i++) { if(last<seg[i].l) { cnt++; //若下一个区间左端点比上一个区间的右端点小,那么就要再新加一个圆 last=seg[i].r; //更新 } } cout<<cnt; } getchar();getchar(); return 0; }~111~ ~定过~
 
信息
- ID
 - 24
 - 时间
 - 1000ms
 - 内存
 - 128MiB
 - 难度
 - 1
 - 标签
 - 递交数
 - 159
 - 已通过
 - 107
 - 上传者