# POJ 1328 Radar Installation C语言版

POJ题解 5427浏览

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

Slyar:说一下题意。假设有一条无限长的海岸线，海岸线以上部分有n个岛屿。在海岸线上有雷达，每个雷达能够探测的范围为半径为d的圆，当且仅当一个岛屿与雷达的距离小于等于d时，岛屿能被雷达探测到。给出所有岛屿的坐标和雷达的半径。求最少需要用多少个雷达，使得所有的岛屿都被探测到。

```#include
#include
#include

typedef struct
{
double left;
double right;
}point;

point p[1001];
int n, d, sum;

/* 按左坐标排序 */
int cmp(const void *a, const void *b)
{
return (*(point*)a).left >= (*(point*)b).left ? 1 : -1;
}

void Solve()
{
int i;
double std;
/* 对岛坐标进行排序 */
qsort(p, n, sizeof(point), cmp);
sum = 1;
/* 标准值为第一个点右坐标 */
std = p[0].right;
/* 从最左边开始扫描 */
for (i = 1; i < n; i++)
{
/* 某点左坐标比标准值大则雷达 + 1，更新标准值为该点右坐标 */
if (p[i].left > std)
{
std = p[i].right;
sum++;
}
else
{
/* 某点右坐标比标准值小，更新标准值为该点右坐标 */
if (p[i].right < std)
{
std = p[i].right;
}
}
}
}

int main()
{
int x, y, i, t, fail;
double l;
t = 1;
while(1)
{
fail = 0;
scanf("%d%d", &n, &d);
if(n + d == 0) break;
for (i = 0; i < n; i++)
{
scanf("%d%d", &x, &y);
/* 若岛超出雷达范围则标记失败 */
if (y > d)
{
fail = 1;
}
else
{
/* 求出雷达范围X轴方向上岛的临域 */
l = sqrt((double)(d * d - y * y));
/* 岛可安雷达的最左坐标 */
p[i].left = x - l;
/* 岛可安雷达的最右坐标 */
p[i].right = x + l;
}
}
if (fail)
{
sum = -1;
printf("Case %d: %d\n", t++, sum);
}
else
{
Solve();
printf("Case %d: %d\n", t++, sum);
}
}
//system("pause");
return 0;
}
```

### 网友最新评论 (8)

1. @exmorning 随便啦随便啦，我现在也没时间看哪个对，你觉得错了就错了吧，呵呵。
Slyar11年前 (2010-12-10)回复
2. 这代码貌似错了，例：[0 4],[3 7],[6 10],这3个区间的雷达数应该是2，而不是1。而你的代码所得的值是1。
exmorning11年前 (2010-12-10)回复
3. @Slyar 我用的是C++。。。
匿名11年前 (2010-08-24)回复
4. @ 刚试验了，用G++，如果只是按你说的修改，我全部AC了
Slyar11年前 (2010-08-23)回复
5. @Slyar 我在PKU上提交，一个ＷＡ，一个AC，就是这样。。。
匿名11年前 (2010-08-23)回复
6. @ 恩？两个是一样的，没有任何不同，你WA估计是别的原因。
Slyar11年前 (2010-08-23)回复
7. 好棒！
匿名11年前 (2010-08-23)回复
8. 如果没有把qsort()写在函数Solve（）内，而是写在主函数内，即： else { qsort(p, n, sizeof(point), cmp); Solve(); printf("Case %d: %d\n", t++, sum); } 提交后为什么是wrong answer？我甚是不解，求助！！！
匿名11年前 (2010-08-23)回复