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
- 难度
- 2
- 标签
- 递交数
- 137
- 已通过
- 89
- 上传者