UVa 10382 喷水装置(贪心)
2024-10-10 05:17:53
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;
}
}
最新文章
- AWS开发人员认证考试样题解析
- H5拍照应用开发经历的那些坑儿
- 转:Task任务调度实现生产者消费者模式 (个人理解后文)
- Log4j写日志文件使用详解
- Haskell 与范畴论
- ylbtech-dbs:ylbtech-2,PAM(个人资产管理系统)
- Thread.sleep() &; SystemClock.sleep()
- Oracle 11g gateways(透明网关)配置
- Ambari2.5.3卸载smartsense
- PDF怎么添加文字水印与图片水印
- 分布式监控系统开发【day37】:服务端生成配置数据(四)
- bilinear pooling
- multipart/form-data和application/x-www-form-urlencoded区别
- cURL模拟POST提交数据
- 五、Oracle 分组查询、视图
- Properties读取properties配置文件
- 如何在Mac的Finder中显示/usr,/tmp,/var等隐藏目录
- django项目添加utf-8编码支持中文
- C#获取网页的HTML码、下载网站图片
- java sendmail
热门文章
- mac下多个php版本快速切换的方法
- SparkSQL UDF两种注册方式:udf() 和 register()
- [LeetCode] 821. Shortest Distance to a Character_Easy tag: BFS
- .net 调用API并解析Json数据方法
- Openstack创建虚拟机 Restful api和RPC调用
- php ci 报错 Object not found! The requested URL was not found on this server. If you entered the URL manually please check
- iOS开发之AFNetworking实现数据传输和文件上传
- [转载]ViewState使用小结
- Python之路----内置函数补充与匿名函数
- ELK学习笔记之CentOS 7下ELK(6.2.4)++LogStash+Filebeat+Log4j日志集成环境搭建