题意:在一条线段上选出尽量少的点,使得和所有给出的n个点距离不超过D。

分别计算出每个点在线段的满足条件的区间,然后就转化成了区间选点的问题了,按照右端点排序,相同时按照左端点排序,按照之前的排序一定保证了包含这个点的区间是连续的。贪心,每次选右边的端点,维护一个当前选择点的位置,每遇到区间就判断一下并更新一下点的位置。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+;
struct seg
{
double l,r;
bool operator < (const seg& x) const{
return r < x.r || (r == x.r && l > x.l);
}
}S[maxn]; int main()
{
int L,D,N;
while(~scanf("%d%d%d",&L,&D,&N)){
double dis = D;
for(int i = ; i < N; i++){
double x,y; scanf("%lf%lf",&x,&y);
double r = sqrt(dis*dis-y*y);
S[i].l = x-r;
S[i].r = x+r;
}
sort(S,S+N);
double cur = -1e9;
int ans = ;
for(int i = ; i < N; i++){
if(cur < S[i].l) {
cur = S[i].r < L ?S[i].r : L;
ans++;
}
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. XML技术之SAX解析器
  2. git commit 代码时提示: Warning: Your console font probably doesn‘t support Unicode.
  3. oracle 调用java
  4. css基础不扎实
  5. 对于大数据量的Json解析
  6. time模块
  7. [Leetcode] Next Permutation
  8. eclipse启动无响应,停留在Loading workbench状态
  9. Hadoop伪分布模式配置
  10. Cocos2d-x中由sprite来驱动Box2D的body运动(用来制作平台游戏中多变的机关)
  11. codeforces #313 div1 C
  12. [Gauss]POJ1681 Painter&#39;s Problem
  13. delphi 预览图片2 (MouseUP)
  14. java学习笔记之字符流文件复制
  15. selenium+chrome抓取淘宝搜索抓娃娃关键页面
  16. 关于JavaScript(脚本语言)
  17. Postman中x-www-form-urlencoded请求K-V的ajax实现
  18. web前端(7)—— 了解CSS样式,引入css样式的方式
  19. day 51 js-2 函数,对象,正则 (定时器示例)
  20. JavaWeb开发如何用Tomcat部署发布

热门文章

  1. bootstrap下拉框式标签页
  2. 7.10实习培训日志-markdown Git
  3. AI决策算法 之 GOAP (三)
  4. 3分钟简单了解 prototype 和 __proto__
  5. 题解 P1854 花店橱窗布置
  6. 项目模板eShopOnContainers
  7. ASP.NET Core性能测试
  8. 060 Permutation Sequence 排列序列
  9. 2017年3月14日-----------乱码新手自学.net 之Authorize特性与Forms身份验证(登陆验证、授权小实例)
  10. c# 串口操作