POJ 1328 Radar Installation(经典贪婪)
2024-08-23 12:41:51
Radar Installation
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 54143 | Accepted: 12178 |
Description
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the
sea can be covered by a radius installation, if the distance between them is at most d.
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write
a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
Figure A Sample Input of Radar Installations
sea can be covered by a radius installation, if the distance between them is at most d.
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write
a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
Figure A Sample Input of Radar Installations
Input
The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing
two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.
The input is terminated by a line containing pair of zeros
two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.
The input is terminated by a line containing pair of zeros
Output
For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.
Sample Input
3 2
1 2
-3 1
2 1 1 2
0 2 0 0
Sample Output
Case 1: 2
Case 2: 1
算法分析:
刚開始不知道从哪分析,后经指点发现圆心位置是个突破口。首先得出每个点所相应的圆心位置,注意若想覆盖最多。每个圆都尽量做到使点刚好位于圆边界。比方我们左右两边各有一个水果。我们不确定是否能拿得到两个,为了使得尽量拿到两个,我们会使左手刚好触碰到一个。伸右手去抓还有一个,而不是直接以某一个为中心而忽略增大自身所能更加接近还有一个的机会,于是问题就变成了求解圆心。依照圆心排序,不断更新雷达圆心,终于使数量最小。
此外,注意代码凝视部分。。
。
圆心竖轴为0,横轴坐标计算公式:
r=x+sqrt(d*d-y*y)//圆心从左向右移动
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; typedef struct island{
int x;
int y;
double z;
}island;
island land[1000];
int Comp(island a,island b)
{
return a.z<b.z;
}
int main()
{
int n,d,i,count,num=1,sign;
while(cin>>n>>d)
{
sign=0;
if(!(n||d))
break;
count=1,i=0;
while(i<n)
{
cin>>land[i].x>>land[i].y;
land[i].z=(double)land[i].x+sqrt(double(d*d-land[i].y*land[i].y)); //圆心必须浮点数啊有木有
if(abs(land[i].y)>d||d<=0) //注意。当雷达无法笼罩时的情况输出-1
sign=1;
i++;
}
if(sign)
{cout<<"Case "<<num<<": -1"<<endl;num++;continue;}
sort(land,land+n,Comp); //对圆心位置从左到右进行排序
i=1;
double a=land[0].z;
while(i<n)
{
if(!((land[i].x-a)*(land[i].x-a)+land[i].y*land[i].y<=d*d))
{
a=land[i].z;
count++;
}
i++;
}
cout<<"Case "<<num<<": "<<count<<endl;
num++;
}
return 0;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。
最新文章
- 后缀数组 UVA 11107 Life Forms
- jquery mobile转场时加载js失效(转)
- UVa 10285 Longest Run on a Snowboard【记忆化搜索】
- VMware linux与windows文件共享
- xmbc 资源
- 《android开发艺术探索》读书笔记(十)--Android的消息机制
- AngularJS进阶(十八)在AngularJS应用中集成科大讯飞语音输入功能
- MySQL基于ROW格式的数据恢复
- 【maven】依赖、继承、聚合
- Array and Colon in Matlab
- bcrelay广播包转发器
- 20155210 Exp5 MSF基础应用
- webpack 支持的模块方法
- OpenResty 高阶实战之————Redis授权登录使用短连接(5000)和长连接(500W) 使用连接池AB压力测试结果
- JSONObject.parseObject(jsonStr);和JSONObject.fromObject(jsonStr);
- 编译原理之正则表达式转NFA
- HDUOJ---Piggy-Bank
- 查看磁盘读写:iostat
- C++11新特性之七——final/override控制
- Hadoop案例(四)倒排索引(多job串联)与全局计数器
热门文章
- [Angular] Implementing A General Communication Mechanism For Directive Interaction
- Java性能优化技巧集锦
- 关于Altium Designer的一些设置
- 14、USB摄像头(V4L2接口)的图片采集
- Java中关键字throw和throws的区别
- CSS Reset的相关概念及实例
- 多校 hdu
- php实现Bloom Filter
- Android 从硬件到应用:一步一步向上爬 4 -- 使用 JNI 方法调硬件驱动
- 《JavaScript &;amp; jQuery交互式Web前端开发》之JavaScript基础指令