POJ 1328 Radar Installation c++版

发表于 更新于

题目链接：http://poj.org/problem?id=1328

题意要求我们根据所给的坐标的点，选出最少得雷达安装数，若超出范围则为-1。

参考解题报告，应该利用贪心算法，先排出每个点的雷达安装范围，也就是结构体中的left和right，由左到右摆放雷达，用std表示雷达的最远安装范围，在范围不够的时候加设一台，然后更新雷达覆盖范围，这样就能够求出雷达的最小值，其中的细节还需好好研究下，更新标准点的算法是重点！
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cmath>

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

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

void Solve()
{
	int i;
	sum = 1;
	point temp;
	double std;
	//对岛坐标进行排序
	for (int m=0;m<n;m++)
		for(int j=m+1;j<n;j++)
			if (p[m].left>p[j].left)
			{
				temp=p[m];
				p[m]=p[j];
				p[j]=temp;
			}
	std = p[0].right;
	//第一个点的右坐标作为起始参考
	for (i = 1; i < n; i++)
	{
		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;
	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
			{
				//求出这个点最远的雷达点
				p[i].left = x - sqrt((double)(d * d - y * y));
				p[i].right = x + sqrt((double)(d * d - y * y));
			}
		}
		if (fail)
		{
			printf("Case %d: -1n", t++);
		}
		else
		{
			Solve();
			printf("Case %d: %dn", t++, sum);
		}
	}
}