Radar Installation
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 52444 | Accepted: 11792 |
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
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
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
题意:
给出 n(1 ~ 1000),d,后给出 n 个坐标点,问在 x 轴上选择一些点,这些点能覆盖周围半径 d 以内的地方,问最少在坐标轴上建立几个点,使之能覆盖所有给出的点,如果不能则输出 -1。
思路:
贪心。找出最少的点数,使之覆盖所有的区间。对于每个给出的点,在半径 d 以内都会在 x 轴上有一个区间范围,找出所有点的区间范围之后。题目变为求解找到最少的点使之所有区间得到覆盖的问题。先对所有区间范围的左坐标由小到大排序一遍,维护最右的端点值,如果下一个区间的左边大于当前右端点值,则需要增加一个点,且维护的最右端点值变为该区间的右端点值。还有一个值得注意的地方就是,如果这个区间的右端点值小于当前维护的右端点值,则需要更新这个端点值。如果在计算区间的时候,遇到 y > d 的则可以判断为 -1 输出。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef struct { double a, b; } node; node no[1005]; double dis (double a, double c) { double res = c * c - a * a; if(res < 0) return -1; return sqrt(res); } bool cmp (node a, node b) { return a.a < b.a; } int main() { int n, t = 0; double c; while (~scanf("%d%lf", &n, &c) && n && c) { int temp = 0; memset(no, 0, sizeof(no)); for (int i = 0; i < n; ++i) { double x, b; scanf("%lf%lf", &x, &b); if (b > c) temp = 1; else { double a = dis(b, c); no[i].a = x - a; no[i].b = x + a; } } printf("Case %d: ", ++t); if (temp) printf("-1\n"); else { sort(no, no + n, cmp); int ans = 1; double ee = no[0].b; for (int i = 1; i < n; ++i) { if (no[i].b < ee) ee = no[i].b; else if (no[i].a > ee) { ++ans; ee = no[i].b; } } printf("%d\n", ans); } } return 0; }
相关推荐
北大POJ1328-Radar Installation 解题报告+AC代码
Radar Signals: An Introduction to Theory and Application introduces the reader to the basic theory and application of radar signals that are designated as large time-bandwidth or pulse-compression ...
William L. Melvin 的著作, Principles of Modern Radar 第三部分, Radar Applications 仅供学习交流使用,请勿用于其他用途
Synthetic Aperture Radar Processing" simply and methodically presents principles and techniques of Synthetic Aperture Radar (SAR) image generation by analyzing its system transfer function. The text ...
A practical tool on radar systems that will be of major help to technicians, student engineers and engineers working in industry and in radar research and development. The many users of radar as well ...
Radar Signal Analysis and Processing Using MATLAB 2009 年新书源码Bassem R. Mahafza Features Provides comprehensive coverage of radar signals and signal processing techniques and algorithms Presents ...
Delphi Electronically Scanning Radar
Waveform diversity: a way forward to the future of the radar A. De Maio, A. Farina, F. Gini, L. Patton and M.Wicks Chapter 1 Classical radar waveform design Nadav Levanon Chapter 2 Information ...
雷达,是英文Radar的音译,源于radio detection and ranging的缩写,意思为"无线电探测和测距",即用无线电的方法发现目标并测定它们的空间位置。因此,雷达也被称为“无线电定位”。雷达是利用电磁波探测目标的电子...
fundamentals of radar signal processing fundamentals of radar signal processing
Tracking radar targets with multiple reflection points
Polarimetric.Radar.Imaging 极化雷达成像 英文原版
Peter Knee-Sparse Representations for Radar with MATLAB Examples
Simulation is integral to the successful design of modern radar systems, and there is arguably no better software for this purpose than MATLAB. But software and the ability to use it does not ...
Principles of Modern Radar Advanced Techniques IEEE
经典书籍RADAR SIGNALS Matched Filter;Ambiguity Function;Basic Radar Signals;Frequency-Modulated Pulse。。。
fmcw radar broadband radar 4G guide
this is a book for radar signal processing