这个点就是贪心策略中的区间选点问题。
把右端点从大到小排序， 左端点从小到大排序。
每次取区间右端点就可以了， 到不能覆盖的时候就ans++， 重新取点
ps：这道题不考虑精度也可以过
要着重复习一下区间相关问题了， 包括前面没有例题的知识点的部分
#include#include #include #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 112345;struct node{ double l, r; node(double l = 0, double r = 0) : l(l), r(r) {}}a[MAXN];double L, dis;int n;void add(int i, double x, double y){ double t = sqrt(dis * dis - y * y); double l = x - t, r = x + t; a[i] = node(l, r);}bool cmp(node a, node b){ if(a.r != b.r) return a.r < b.r; return a.l > b.l;}int main(){ while(~scanf("%lf%lf%d", &L, &dis, &n)) { REP(i, 0, n) { double x, y; scanf("%lf%lf", &x, &y); add(i, x, y); } sort(a, a + n, cmp); int ans = 1; double ma = a[0].r; REP(i, 1, n) if(a[i].l > ma) { ans++; ma = a[i].r; } printf("%d\n", ans); } return 0;}