一、题意

给一个x轴的一段长度[0, L]代表一条公路，然后给出n个点的坐标(xi, yi)，要你在公路上选出尽量少的点，使得对于给定的每个点，都有一个选出的点离它的欧几里得距离不超过D。

二、解析

以每个给定的点为圆心，D为半径可以画出n个⚪，这些⚪和公路会相交并得到对应的割线。这些割线就是本题中的区间。问题就变成了，在这n个区间中，选出尽量少的点，使得每个区间都至少包含一个点。
这就是典型的区间选点问题了。

根据贪心的思想，我们将区间按照右端点从小到大排列，由于如果一个大区间完全包含一个小区间，则点显然是要选在小区间里，因此像“二”型这样的两个区间，选点选在右端点小的那个区间中准没错；剩下需要考虑的情况就是左右端点都同时递增的区间关系，这种情况显然也是选点选在右端点小的那个区间中准没错，因为这样这个点就能涵盖这两个区间了。

因此我们的贪心策略是：按右端点排序后，总是选取第一个不被包含的区间的最右端点处。

三、代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define mp make_pair
using namespace std;
using pdd = pair<double, double>;
int L, D, n;
vector<pdd> vec;  // 存放割线区间

int main() {
    while(cin >> L >> D >> n) {
        vec.clear();
        for(int i = 0, x, y; i < n; i ++) {
            cin >> x >> y;
            double a = sqrt(D * D - y * y), l = x - a, r = x + a;
            l = min((double)L, max((double)0, l)), r = min((double)L, max((double)0, r));
            vec.push_back(mp(l, r));
        }
        sort(vec.begin(), vec.end(), [](const pdd& a, const pdd& b) {
            return a.second < b.second;
        });
        int ans = 0;
        double cur = -1;
        for(const auto& p : vec) if(cur < p.first || cur > p.second) ans ++, cur = p.second;
        cout << ans << endl;
    }
}

四、归纳

  • 区间选点问题：按右端点排列，总是选取第一个还没有被涵盖的区间的右端点。