poj 1328 安雷达问题 贪心算法

题意：雷达如何放置？在xoy二维平面坐标系里面，x轴上方的为岛屿，x轴下方的是雷达要放到位置，如何放使得雷达放的最少？

思路

1. 肯定放在x轴上减少浪费是最好的选择
2. 什么情况下，雷达无法到达呢？--以这个岛屿为圆心，d为半径，如果这个圆与x轴没有交点的话，就是无法覆盖到---即y>d
3.   现在就可以这么想了，每个岛屿都当成圆心C，然后都取画圆，跟x轴的交点例如交点A,B.如果雷达放到AB之间那就是可以将刚才C覆盖住了。--转为区间贪心问题

区间贪心问题：

1. 先将各个区间的左端点按照从小到大排序
2. 然后按递增序列开始选取区间，有两种情况 实例说明

pos---为当前位置 lefe，right分别为当前区间的左右端点

if(pos<left){ num++；pos=right;}

if(pos>right) {pos=right;}

注：针对本题num为雷达的数量

数学方法

C(x,y) 圆的方程(X-x)^2+(Y-y)^2=d^2   与x轴的交点为 x+根号(d^2-y^2) ，x-根号(d^2-y^2)

解题代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
using namespace std;
typedef struct Node
{
    double left, right;
}node;
int cmp(node a, node b)
{
    return a.left < b.left;
}
int x[2100], y[2100];
node dis[2100];
int main()
{
    int n, d;
    double z;
    int ans = 0;
    while (scanf("%d%d", &n, &d) != EOF)
    {
        if (n == 0 && d == 0)
            break;
        else
        {
            int flag = 1;
            ans++;
            for (int i = 0; i < n; i++)
            {
                scanf("%d%d", &x[i], &y[i]);
                if (y[i] > d)
                    flag = 0;
                else
                {
                    z = sqrt(d*d*1.0 - y[i] * y[i] * 1.0);
                    dis[i].left = x[i] - z;
                    dis[i].right = x[i] + z;
                }
            }
            if (!flag)
            {
                printf("Case %d: -1
", ans);
            }
            else
            {
                sort(dis, dis + n, cmp);
                int num = 0;
                double p = -1000000;
                for (int i = 0; i < n; i++)
                {
                    if (dis[i].left > p)
                    {
                        num++;
                        p = dis[i].right;
                    }
                    else if (dis[i].right < p)
                    {
                        p = dis[i].right;
                    }
                }
                printf("Case %d: %d
", ans, num);
            }
        }
    }
    return 0;
}