最新消息:点击查看大S的省钱秘笈

POJ 1328 Radar Installation C语言版

POJ题解 Slyar 4901浏览 8评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

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.

1328

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时,岛屿能被雷达探测到。给出所有岛屿的坐标和雷达的半径。求最少需要用多少个雷达,使得所有的岛屿都被探测到。

使用贪心+快排,0MS过了。求出每个岛屿对应圆心在x轴上的范围,对左坐标排序后贪心选择。类似于:数轴上有N个点,要用几个单位长度区间才能将它们全部覆盖?具体实现见代码注释。

这次用到了C语言的库函数qsort,写cmp函数的时候要注意浮点数的比较。另外这个排序只需要考虑左坐标即可,因为就算左坐标相同也不会影响结果,贪心算法会自动更正右坐标的选择。

#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;
}

转载请注明:Slyar Home » POJ 1328 Radar Installation C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (8)

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