题目描述
描述:
假设海岸线是一条无限延伸的直线。它的一侧是陆地,另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上(包括海岸线),并且每个雷达都有相同的扫描范围d。你的任务是建立尽量少的雷达站,使所有小岛都在扫描范围之内。
数据使用笛卡尔坐标系,定义海岸线为x轴。在x轴上方为海洋,下方为陆地。
样例1如图所示
输入输出格式
输入格式:
第一行包括2个整数n和d,n是岛屿数目,d是雷达扫描范围。
接下来n行为岛屿坐标。
输出格式:
一个整数表示最少需要的雷达数目,若不可能覆盖所有岛屿,输出“-1”。
输入输出样例
3 2
1 2
-3 1
2 1
2
贪心,把问题转化成岛屿覆盖的区域必须有雷达,之后类似于活动安排问题
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std; #define N 1005
int n,d;
struct island{
int x;int y;
}is[N];
struct miku{
double l,r;
bool operator < (const miku & a)const{
return r < a.r;
}
}cd[N];
double calc(double x)
{
return sqrt(1.0*d*d-x*x);
}
bool vis[N];
int main()
{
cin>>n>>d;
for(int i=;i<=n;i++)
{
cin>>is[i].x>>is[i].y;
if(is[i].y>d||d<){cout<<"-1"<<endl;return ;}
}
for(int i=;i<=n;i++)
{
double len=calc(is[i].y);
cd[i].l=is[i].x-len;
cd[i].r=is[i].x+len;
}
sort(cd+,cd+n+);
int ans=;
for(int i=;i<=n;i++)
{
if(!vis[i])
{
vis[i]=;
for(int j=;j<=n;j++)
{
if(!vis[j] && cd[j].l<=cd[i].r)
vis[j]=;
}
ans++;
}
}
cout<<ans<<endl;
return ;
}
luogu P1325 雷达安装的更多相关文章
-
洛谷 P1325 雷达安装 解题报告
P1325 雷达安装 题目描述 描述: 假设海岸线是一条无限延伸的直线.它的一侧是陆地,另一侧是海洋.每一座小岛是在海面上的一个点.雷达必须安装在陆地上(包括海岸线),并且每个雷达都有相同的扫描范围d ...
-
落谷p1325雷达安装(计算几何)
传送门 //p1325雷达安装 //很明显雷达应该安装在海岸线上 //而为了满足一个点被覆盖那在区间[x - sqrt(d ^ 2 - y ^ 2), x + sqrt(d ^ 2 - y ^ 2)] ...
-
P1325 雷达安装
传送门 思路: 采取贪心的思想. 把每个岛屿看作圆心,以雷达的范围 d 为半径,求出与 x 轴的左右两个交点,两交点所夹的区间就需要放置一个雷达,这样就把这道题转换为了区间取点问题.在枚举岛屿时,记录 ...
-
luogu 1325 雷达安装
题目链接 题意 在\(x\)轴上方有\(n\)个海岛,要在\(x\)轴建雷达,每个雷达的覆盖范围为半径为\(d\)的圆,问至少要建多少个雷达能覆盖所有海岛. 思路 对于每个海岛计算出雷达建立在什么范围 ...
-
洛谷P1325 雷达安装
题目 考虑对于一个小岛,如果有雷达可以覆盖它,则这些雷达肯定在一个区间里,则原题内容则变为区间选点问题 #include <bits/stdc++.h> using namespace s ...
-
Libre 6009 「网络流 24 题」软件补丁 / Luogu 2761 软件安装问题 (最短路径,位运算)
Libre 6009 「网络流 24 题」软件补丁 / Luogu 2761 软件安装问题 (最短路径,位运算) Description T 公司发现其研制的一个软件中有 n 个错误,随即为该软件发放 ...
-
【luogu1325】雷达安装--贪心
题目描述 描述: 假设海岸线是一条无限延伸的直线.它的一侧是陆地,另一侧是海洋.每一座小岛是在海面上的一个点.雷达必须安装在陆地上(包括海岸线),并且每个雷达都有相同的扫描范围d.你的任务是建立尽量少 ...
-
Poj1328Radar Installation雷达安装
原题链接 经典贪心,转化为问题为,对于所有的区间,求最小的点数能使每个区间都至少有一个点. #include<iostream> #include<cstdio> #inclu ...
-
Greedy:Radar Installation(POJ 1328)
装雷达 题目大意,就是令在海岸线的(直线)一边是海(y>0),另一边是陆地(y<=0),在海岸线上装雷达,雷达可以覆盖的范围为d,海上有岛,(x,y),问你应该怎么装雷达,才能做到技能雷达 ...
随机推荐
-
很赞的MathJax
一直想在网页上放进LaTeX布局,但由于是要发布在SAE上,因此有很多的限制. 然后在这儿发现了这个好东东,MathJax,非常方便,JS直接可以外链. 通过它,我编辑了这个页面,看起来很不错哦.
-
Linux makefile教程之后序十一[转]
后序 —— 终 于到写结束语的时候了,以上基本上就是GNU make的Makefile的所有细节了.其它的产商的make基本上也就是这样的,无论什么样的make,都是以文件的依赖性为基础的,其基本是都 ...
-
Pomodairo,番茄工作法-应用篇
传统: 选择一个待完成的任务 将番茄时间设为适合自己的固定时间 专注工作,中途不允许做任何与该任务无关的事,直到番茄时钟响 ...
-
JavaEE自定义标签:标签类的创建、tld配置文件的创建(位置、如何创建)、Web-XML配置、JSP应用
1.标签 以类似于html标签的方式实现的java代码的封装. 第一:形成了开发标签的技术标准---自定义标签的技术标准. 第二:java标准标签库(sun之前自己开发的一系列的标签的集合)jstl, ...
-
安卓TCP通信版本2
PC做服务器,安卓做客户端. 安卓获取输入框的内容并发送,然后等待接收服务器的消息 服务器先行开启,接收到客户端的数据,然后回复消息. 实现了对线程类的封装,通过按钮启动线程发送并接收 服务器代码(j ...
-
[物理学与PDEs]第5章第3节 守恒定律, 应力张量
5. 3 守恒定律, 应力张量 5. 3. 1 质量守恒定律 $$\bex \cfrac{\p \rho}{\p t}+\Div_y(\rho{\bf v})=0. \eex$$ 5. 3. 2 应 ...
-
入手Docker容器注意事项:命令结束容器退出
在没有 docker 容器的时候,在终端(terminal)中运行 shell 命令,我们知道当终端退出时(比如关闭终端窗口或退出 ssh 会话),终端中执行的命令也会结束.所以,当我们在终端中执行持 ...
-
防止短时间js 重复执行
function debounce(fn, delay) { // 持久化一个定时器 timer let timer = null; // 闭包函数可以访问 timer return function ...
-
python爬虫 抓取一个网站的所有网址链接
sklearn实战-乳腺癌细胞数据挖掘 https://study.163.com/course/introduction.htm?courseId=1005269003&utm_campai ...
-
(转)Unity3d UnityEditor编辑器定制和开发插件
在阅读本教程之前,你需要对Unity的操作流程有一些基础的认识,并且最好了解内置的GUI系统如何使用. 如何让编辑器运行你的代码 Unity3D可以通过事件触发来执行你的编辑器代码,但是我们需要一些编 ...