1.概述
原题的意思是，给定两个整型数字n(1<=n<=1000)和一个d（表示雷达的识别距离）。然后接下来的n行分别有两个数x,y表示岛I(i)的坐标（x,y）其中个i(1<=i<=n)，你的目标是求可以覆盖所有岛屿的最少的雷达数量（雷达只能放在x轴上）。
2.我的想法
首先利用一个结构体point, 其中每一个x，y，mixx和maxx分别表示横坐标，纵坐标，以d为半径的且以圆心在x轴的雷达的位置的最小值以及最大值。
然后可以通过排序points（比较minx的位置确定循环的开始的位置）。
然后分别讨论几种情况：
设right表示第一次放雷达的位置（最左端的岛屿，为了能够最大覆盖，需要从maxx开始放置）。
假设下一个岛屿的索引是i+1（起始位置从i+1开始）：
- 如果points[i+1].mixx > right 很显然I(i+1)是放置在right雷达覆盖不了的，所以需要增加雷达的数量，同时把雷达放在points[i+1].maxx上，（图1-1）。
- 很显然，如果points[i+1] <=tight 那么right位置的雷达是可以覆盖的，那我不管他（图1-1）。
- 如果points[i+1].mixx <=right 且points[i+1].maxx < right。也就是图1-2的情况，算法只要将雷达重新放在points[i+1].maxx上。就okay。
3.附上代码（但是无法AC。郁闷）
#include "stdio.h"
#include "stdlib.h"
#include <cmath>
#define N 1001
#include <algorithm>
struct point {
int x; int y;
int minx; int maxx;
};
point points[N];
//POJ 1328
//贪心算法 我认为是可以的 但是还是不行 奇怪了
int res[N];
int np, d;
bool cmp(const point &l, const point &p)
{
return l.minx < p.minx;
}
bool set_min_xpoint(point *dest)
{
int mm, mmmax;
bool flag = false;
if (dest->y > d)
{
flag = true;
}
else
{
int sr = sqrt(d*d-dest->y *dest->y);
dest->minx = dest->x- sr;
dest->maxx = dest->x+ sr;
flag = false;
}
return flag == false;
}
int main()
{
int pos = 0;
while (~scanf("%d %d", &np, &d) && (np != 0 && d != 0))
{
bool res1 = true;
for (int i = 0; i<np; ++i)
{
scanf("%d %d", &points[i].x, &points[i].y);
if (!set_min_xpoint(&points[i]))
{
res1 = false;
continue;
}
//printf("---%d %d\n", points[i].minx, points[i].maxx);
}
if (res1 == false)
{
printf("Case %d: %d\n", ++pos, -1);
continue;
}
std::sort(points, points + np, cmp);
/*
int sum = 1;
for (int i = 0; i < np - 1; ++i)
{
if (points[i + 1].minx >= points[i].minx && points[i + 1].minx <= points[i].maxx)
{
--sum;
}
}
*/
//选取之前放置雷达的位置 然后查找下一个的左端点是否在当前的右边界的：1.右边：那么在当前位置的右边放下雷达
//2.左边：那么肯定是可以覆盖的
//如果下一个的位置的右边界在之前放置雷达的位置左边 那么就要在这个的最大位置放置雷达 那么之前的都可以覆盖了
//如果在右边也在覆盖范围内
int sum = 1;
int right = points[0].maxx;
for (int i = 0; i < np - 1; ++i)
{
if (points[i + 1].minx > right)
{
++sum;
right = points[i + 1].maxx;
}
else if(points[i+1].maxx < right)
{
right = points[i + 1].maxx;
}
}
//*/
printf("Case %d: %d\n", ++pos, sum);
}
return 0;
}