题目大意：有一条沿x轴正方向，长为L的高速公路，n个村庄，要求修建最少的公路出口数目，使得每个村庄到出口的距离不大于D。

题目分析：区间选点问题。在x轴上，到每个村庄距离为D的点有两个（超出范围除外），这两个点便构成了一个区间，这样的区间总共有n个。问题便转化为了，在n个区间中选取最少的点占据所有区间。贪心即可，贪心策略：将所有区间按右端点排序，若需要选择，每次都选区间右端点。

 

代码如下：

# include
     
      # include
      
       # include
       
        # include
        
         # include
         
          # include
          
           using namespace std;struct Q{ double l,r; Q(double _l,double _r):l(_l),r(_r){} bool operator < (const Q &a) const { return r
           
            v;void dist(int x,int y,double &l,double &r){ l=(double)x-sqrt((double)D*(double)D-(double)y*(double)y); r=(double)x+sqrt((double)D*(double)D-(double)y*(double)y);}int solve(){ int ans=0; double p=-1.0; for(int i=0;i
            
             v[i].r){ ++ans; p=v[i].r; } } return ans;}int main(){ int x,y; double li,ri; while(scanf("%d",&L)!=EOF) { scanf("%d%d",&D,&n); v.clear(); for(int i=0;i