POJ:1328-Radar Installation
Radar Installation
Time Limit: 1000MS Memory Limit: 10000K
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.
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
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
题意就是在x轴上方很多个点,要求用圆心在x轴上半径为r的圆将这些点覆盖,问最少要用多少个圆。这是一个很好的题。
一开始知道这是一个贪心,但是贪心的方法很久都没想到。其实就是先将这些点按照x坐标排序,然后确定第一个点的圆心,然后看第二个点圆能够建立圆心区域的最左边是否在第一个圆心的左边,是则将第二个圆心替换第一个圆的圆心,如果不是就看第二个点是否在第一个圆内,如果在圆内则不用管,不在就需要建一个新的圆来包含这个点,然后依次类推就可以得到最佳答案。输出-1就是y轴上的坐标比给出的r还更大。
还有就是要注意一下浮点数精度的问题。
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn = 1010;
struct node
{
int x,y;
} p[maxn];
bool cmp(node a,node b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y > b.y;
}
bool init(int n,int r)
{
bool flag = false;
for(int i=0; i<n; i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
if(p[i].y > r)
flag = true;
}
sort(p,p+n,cmp);
return flag;
}
int solve(int n,int r)
{
double pre_pos = -100000;
int ans = 1;
node now;
queue<node> qu;
for(int i=0; i<n; i++)
qu.push(p[i]);
pre_pos = 0x7f7f7f7f;
while(!qu.empty())
{
now = qu.front();
qu.pop();
double x = now.x + sqrt(r*r - now.y*now.y);
if(x < pre_pos)//圆心替换
{
pre_pos = x;
continue;
}
if((now.x-pre_pos)*(now.x-pre_pos) + now.y*now.y > r*r)//不包含在上一个点的圆内,需要新的圆
{
ans++;
pre_pos = x;
}
}
return ans;
}
int main()
{
int n,r,t = 1;
while(scanf("%d%d",&n,&r))
{
if(n+r == 0)
return 0;
bool flag = init(n,r);
if(flag)
{
printf("Case %d: -1\n",t++);
continue;
}
int ans = solve(n,r);
printf("Case %d: %d\n",t++,ans);
}
}
最新文章
- SpringMVC 入门
- 使用专业的消息队列产品rabbitmq之centos7环境安装
- EditText获取和失去焦点,软键盘的关闭,和软键盘的显示和隐藏的监听
- angular路由配置用法
- 【QT】C++ GUI Qt4 学习笔记2
- JS调用WebService
- tomcat8编码
- HTML5之Canvas绘图实例——饼状图
- asp.net 自定义文本框
- grep in linux
- android--使用Struts2服务端与android交互
- 转载:修改xshell中文乱码的问题(管用)
- 关于Web Api的HelpPage文档注释问题
- mysql的约束的讨论
- PHP headers_sent() 函数
- Java多线程 阻塞队列和并发集合
- [Swift]LeetCode413. 等差数列划分 | Arithmetic Slices
- Ubuntu18 的超详细常用软件安装
- IE CSS Hack【记录】
- SSE图像算法优化系列二十四: 基于形态学的图像后期抗锯齿算法--MLAA优化研究。