poj1328

题目大意：

雷达装置

假设海岸线是一个无限长的直线，大陆在海岸线的一侧，大海在另一侧，每一个小岛在大海中都是一个点，并且安装一些雷达，在沿海航行的时候定位，只能覆盖d距离，所以一个大陆在大海中可以覆盖由半径决定，他们的距离最多是d。

我们使用卡迪尔坐标系统，定义海岸线为x轴，大海在x轴的上面，大陆在x轴的下面，给出每个小岛在大海中的位置，然后给你安装雷达覆盖的距离，你的任务是编写一个程序找出来用最少的安装雷达并且覆盖所有的小岛，一个岛屿由x-y坐标确定。

poj1328

我去原来只能在海岸线上安装，哥哥也是醉了（难度降低非常多）

题目解析：

可以发现找到每个点的在海岸线需求的最左端是多少，然后放一个雷达，判断可以有多少个岛屿在这个半径里面，当然需要先按照最右边达到的距离排序

一直wa，不知道为什么？？？？

*////////////////////////////////////////////////////////////////

#include<stdio.h>

#include<math.h>
#include<algorithm>
using namespace std;

#define maxn 1005
#define INF -1000000000

struct point
{
    double x, y, Lx, Rx;
}p[maxn];

bool cmp(point n1, point n2)
{
   // if(fabs(n1.Rx - n2.Rx) > 1e-10)
        return n1.Rx < n2.Rx;
   // return n1.Rx > n2.Rx;
}

int main()
{
    int n, t=1;
    double d;

    while(scanf("%d%lf", &n, &d), n+d)
    {
        int i, ok=0;

        for(i=0; i<n; i++)
        {
            scanf("%lf%lf", &p[i].x, &p[i].y);
            double k = sqrt(d*d-p[i].y*p[i].y);
            p[i].Lx = p[i].x-k, p[i].Rx = p[i].x+k;

            if(p[i].y > d)
                ok = 1;
        }

        if(ok)
        {
            printf("-1 ");//加上Case %d:
            continue;
        }

        sort(p, p+n, cmp);

        int sum=0;
        double Rx=INF;

        for(i=0; i<n; i++)
        {
            if(p[i].Lx - Rx > 1e-10)
            {
                sum++;
                Rx = p[i].Rx;
            }
        }

        printf("Case %d: %d ", t++, sum);
    }

    return 0;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////

擦，原来输出-1的时候也需要输出Case %d:无语了- -

相关推荐