题解

公路就是x轴，这题其实就是区间选点问题。
以村庄位圆心，D为半径，与x轴两个交点，显然只需要这段区间内选一个点就可以让这个村庄满足题意，所以问题转换为在给定的n个区间中选择最少的点，使得每个区间最少有一个点。

然后就直接贪心一下就可以AC。半夜做题效率确实有点低QWQ

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define repd(i,x,y) for(int i=x;i>=y;--i)
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
const int N=1e5+7;
const double eps=1e-10;
const int inf=0x3f3f3f3f;
typedef pair<double,double> q;
q a[N];
int ans,L,D,n;
int main(){
    while(~scanf("%d%d%d",&L,&D,&n)){
        D*=D;ans=1;
        rep(i,1,n){
            double x,y;
            scanf("%lf%lf",&x,&y);
            double tp=sqrt(D-y*y);
            a[i]=q(x+tp,x-tp);
        }
        sort(a+1,a+n+1);
		double lst=a[1].first;
        rep(i,2,n)if(lst<a[i].second)ans++,lst=a[i].first;
        printf("%d\n",ans);
    }
    return 0;
}