https://vjudge.net/problem/UVA-10382

题意:

有一个长为l,宽为w的草坪,在其中心线不同位置有n个点状的喷水装置,喷水坐标为p,喷水半径为r。求喷到所有草坪的最少喷水装置数量。

思路:

喷水装置的有效面积是图中的矩形部分,由此就把喷水区域变成了区间区域,之后利用贪心就可以了。

 #include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn = + ; int n;
double l, w; struct node
{
double l, r;
}a[maxn]; double cacl(double y)
{
return sqrt(y*y - (w / 2.0)*(w / 2.0));
} bool cmp(node a, node b)
{
return a.l < b.l;
} int main()
{
ios::sync_with_stdio(false);
//freopen("D:\\txt.txt", "r", stdin);
double x, y;
while (cin >> n >> l >> w)
{
int cnt = ;
for (int i = ; i < n; i++)
{
cin >> x >> y;
if (y <= w / 2.0) continue;
double m = cacl(y);
a[cnt].l = x - m;
a[cnt].r = x + m;
cnt++;
}
sort(a, a + cnt, cmp);
int num = ;
int flag = ;
double left = , right = ;
if (a[].l <= )
{
int i = ;
while (i < cnt)
{
int j = i;
//找一个右端坐标最大的
while (j < cnt && a[j].l<=left)
{
if (a[j].r > right)
{
right = a[j].r;
}
j++;
}
if (i == j) break;
i = j;
num++;
left = right;
if (left >= l)
{
flag = ;
break;
}
}
}
if(flag) cout << num << endl;
else cout << "-1" << endl;
}
}

最新文章

  1. AWS开发人员认证考试样题解析
  2. H5拍照应用开发经历的那些坑儿
  3. 转:Task任务调度实现生产者消费者模式 (个人理解后文)
  4. Log4j写日志文件使用详解
  5. Haskell 与范畴论
  6. ylbtech-dbs:ylbtech-2,PAM(个人资产管理系统)
  7. Thread.sleep() &amp; SystemClock.sleep()
  8. Oracle 11g gateways(透明网关)配置
  9. Ambari2.5.3卸载smartsense
  10. PDF怎么添加文字水印与图片水印
  11. 分布式监控系统开发【day37】:服务端生成配置数据(四)
  12. bilinear pooling
  13. multipart/form-data和application/x-www-form-urlencoded区别
  14. cURL模拟POST提交数据
  15. 五、Oracle 分组查询、视图
  16. Properties读取properties配置文件
  17. 如何在Mac的Finder中显示/usr,/tmp,/var等隐藏目录
  18. django项目添加utf-8编码支持中文
  19. C#获取网页的HTML码、下载网站图片
  20. java sendmail

热门文章

  1. mac下多个php版本快速切换的方法
  2. SparkSQL UDF两种注册方式:udf() 和 register()
  3. [LeetCode] 821. Shortest Distance to a Character_Easy tag: BFS
  4. .net 调用API并解析Json数据方法
  5. Openstack创建虚拟机 Restful api和RPC调用
  6. php ci 报错 Object not found! The requested URL was not found on this server. If you entered the URL manually please check
  7. iOS开发之AFNetworking实现数据传输和文件上传
  8. [转载]ViewState使用小结
  9. Python之路----内置函数补充与匿名函数
  10. ELK学习笔记之CentOS 7下ELK(6.2.4)++LogStash+Filebeat+Log4j日志集成环境搭建