POJ 1328 Radar Installation 雷达安装 贪心问题求解

2024-06-08 10:48

本文主要是介绍POJ 1328 Radar Installation 雷达安装 贪心问题求解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接: POJ 1328 Radar Installation

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


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 11 2
0 20 0

Sample Output

Case 1: 2
Case 2: 1

Source

Beijing 2002

题意

在x轴表示的海岸线上需要布置雷达,以覆盖海中的n个海岛,雷达的覆盖半径为d,求解如何选择布置点才能使用到的雷达最少。如果有的海岛不能被覆盖到,那么输出-1。

分析

考察以海岛为圆心,做半径为d的圆,看与x轴相交的那段区间,这样的话,这个区间内的任何位置布置雷达,都是可以覆盖这个海岛的,对于所有的海岛,当然不乏求到的区间有部分重合的情况,那么在这个重合的区间中布置雷达,当然就能覆盖到两个以上的点,这样就能节省雷达,雷达所在的区间越多,节省的雷达就越多。


思想

典型的贪心思想。对于求出的每一个区间,我们进行排序,让区间右端点小的排在前面,如果右端点相等,那么左端点大的排在前面(想想为什么)。

那么该如何选择布置点呢?

首先我们选取排序号后的第一个区间的右端点为第一个布置点,它的位置为st,然后再按顺序找后面的区间。如果当前区间的左端点大于st,说明st位置的雷达不能覆盖到这个海岛,那么雷达数加1,同时更新st为这个区间的右端点。如果当前区间的左端点小于等于st,则说明st位置的雷达能覆盖这个海岛,忽略这个区间。

代码

/*POJ_1328_Radar_InstallationAuthor: Sign_Greedy
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;int n, d;
struct seg
{double l, r;
}SEG[1010];seg pos(int x, int y)
{seg s;s.l = x - sqrt(d*d - y*y);s.r = x + sqrt(d*d - y*y);return s;
}
bool cmp(seg a, seg b)
{if(a.r == b.r) return a.l > b.l;return a.r < b.r;
}
int main()
{int x[1010], y[1010], cas = 1;while(scanf("%d%d", &n, &d), n, d){bool flag = true;for(int i = 0; i < n; i++){scanf("%d%d", &x[i], &y[i]);if(y[i] > d)flag = false;}if(!flag){printf("Case %d: -1\n", cas++);continue;}for(int i = 0; i < n; i++)SEG[i] = pos(x[i], y[i]);sort(SEG, SEG+n, cmp);int cnt = 1;double st = SEG[0].r;for(int i = 1; i < n; i++)if(SEG[i].l > st){st = SEG[i].r;cnt++;}printf("Case %d: %d\n", cas++, cnt);}return 0;
}



这篇关于POJ 1328 Radar Installation 雷达安装 贪心问题求解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1041969

相关文章

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种,单机模式和集群模式以及伪集群模式。 ■ 单机模式:Zookeeper只运行在一台服务器上,适合测试环境; ■ 伪集群模式:就是在一台物理机上运行多个Zookeeper 实例; ■ 集群模式:Zookeeper运行于一个集群上,适合生产环境,这个计算机集群被称为一个“集合体”(ensemble) Zookeeper通过复制来实现

CentOS7安装配置mysql5.7 tar免安装版

一、CentOS7.4系统自带mariadb # 查看系统自带的Mariadb[root@localhost~]# rpm -qa|grep mariadbmariadb-libs-5.5.44-2.el7.centos.x86_64# 卸载系统自带的Mariadb[root@localhost ~]# rpm -e --nodeps mariadb-libs-5.5.44-2.el7

Centos7安装Mongodb4

1、下载源码包 curl -O https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel70-4.2.1.tgz 2、解压 放到 /usr/local/ 目录下 tar -zxvf mongodb-linux-x86_64-rhel70-4.2.1.tgzmv mongodb-linux-x86_64-rhel70-4.2.1/

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

Centos7安装JDK1.8保姆版

工欲善其事,必先利其器。这句话同样适用于学习Java编程。在开始Java的学习旅程之前,我们必须首先配置好适合的开发环境。 通过事先准备好这些工具和配置,我们可以避免在学习过程中遇到因环境问题导致的代码异常或错误。一个稳定、高效的开发环境能够让我们更加专注于代码的学习和编写,提升学习效率,减少不必要的困扰和挫折感。因此,在学习Java之初,投入一些时间和精力来配置好开发环境是非常值得的。这将为我

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s