当前位置:网站首页>Radar equipment (greedy)
Radar equipment (greedy)
2022-07-06 16:08:00 【AC__ dream】
analysis : First, give the location of an island , We can find out the position range where this radar can be placed , It means that as long as the radar is placed in this section , Then the island can be covered by radar , Altogether n An island , Then the corresponding can also be found n Intervals , At this time, there should be at least one radar in each section , But there may be coincidence between intervals Of , In other words, we require a minimum number of radars so that there is at least one radar in each interval , Then this is obviously a greedy problem , Let's sort all the intervals according to the right endpoint , Then we record a r Represents the location of the last radar , If the current range is r To the right of , Then we should at least install another radar , Because there is no longer an island on the left side of the current range that is not covered , So our radar is placed on the right as far as possible , But also within the current range , So it is placed on the right end of the current interval , Place in sequence , Add the number of radars every time you place one 1, Finally, output the number of radars .
Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1003;
int n,d;
struct node{
double l,r;
}p[N];
bool cmp(node a,node b)
{
return a.r<b.r;
}
void f(int i,int x,int y)
{
p[i]={x-sqrt(1.0*d*d-y*y),x+sqrt(1.0*d*d-y*y)};
}
int main()
{
cin>>n>>d;
int x,y;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(y>d)
{
puts("-1");
return 0;
}
f(i,x,y);
}
sort(p+1,p+n+1,cmp);
double r=-9999;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(p[i].l>r)
{
r=p[i].r;
cnt++;
}
}
printf("%d",cnt);
return 0;
}
边栏推荐
- [exercise-3] (UVA 442) matrix chain multiplication
- 1529. Minimum number of suffix flips
- F - birthday cake (Shandong race)
- 渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
- 1903. Maximum odd number in string
- 2027. Minimum number of operations to convert strings
- B - Code Party (girls' competition)
- Information security - threat detection engine - common rule engine base performance comparison
- China potato slicer market trend report, technical dynamic innovation and market forecast
- b站 實時彈幕和曆史彈幕 Protobuf 格式解析
猜你喜欢
滲透測試 ( 1 ) --- 必備 工具、導航
1529. Minimum number of suffix flips
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
[teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
1005. Maximized array sum after K negations
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
Nodejs+vue online fresh flower shop sales information system express+mysql
X-forwarded-for details, how to get the client IP
【高老师软件需求分析】20级云班课习题答案合集
随机推荐
D - function (HDU - 6546) girls' competition
Socket communication
基于web的照片数码冲印网站
Opencv learning log 28 -- detect the red cup cover
栈的经典应用—括号匹配问题
Openwrt source code generation image
想应聘程序员,您的简历就该这样写【精华总结】
初入Redis
【练习-10】 Unread Messages(未读消息)
[exercise -10] unread messages
Hdu-6025-prime sequence (girls' competition)
滲透測試 ( 1 ) --- 必備 工具、導航
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
Quick to typescript Guide
Opencv learning log 16 paperclip count
信息安全-安全编排自动化与响应 (SOAR) 技术解析
Web based photo digital printing website
【练习-1】(Uva 673) Parentheses Balance/平衡的括号 (栈stack)
【高老师软件需求分析】20级云班课习题答案合集
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs