题目传送门(BZOJ)

题解 :

用勾股定理可以 O(1) 的求出一个圆在 X 轴上的两个交点
于是这题就变成了给你一堆区间, 让你放最少的点使得所有区间里都有一个点
按左端点排序, 若上一个点小于当前的左端点, 那么多放一个点, 贪心的使它尽可能的往右
也即放一个点在当前的右端点
如果不小于当前的左端点, 我们就得让它在右端点以内, 若它不在, 相当于把之前的反悔一下, 然后往左一点放
由于当前的这个左端点是排过序的, 所以往左一点放不会影响到之前的区间的答案贡献

代码 :

#include <cmath>#include <cstdio>#include <algorithm>#define f2 doubleusing namespace std;struct LINE { f2 l, r; inline bool operator < (const LINE &A) const {return l < A.l;}}a[101];int main() { f2 cur = -1e9; int n, r, ans = 0; scanf("%d%d", &n, &r); for(int i = 1; i <= n; i ++ ) { int x, y; scanf("%d%d", &x, &y); a[i].l = x-sqrt(r*r-y*y), a[i].r = x+sqrt(r*r-y*y); } sort(a+1, a+n+1); for(int i = 1; i <= n; i ++ ) { if(cur < a[i].l) ans ++, cur = a[i].r; else cur = min(cur, a[i].r); } printf("%d\n", ans);}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<