poj 1328 Radar Installation 贪心

缘起

日常浪费生命 poj 1328 Radar Installation

分析

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
假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达
坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。
要求计算出能够覆盖给出的所有岛屿的最少雷达数目。

【输入】
多样例. 每个样例开头两个数字 n（1<=n<=1000）和d. n是海岛的个数. d是雷达的半径. 然后n行分别是n个
雷达的坐标.输入以(0,0)结束.

【输出】
每个样例输出最少雷达数. 如果办不到, 输出 -1

【样例输入】
3 2
1 2
-3 1
2 1

1 2
0 2

0 0

【样例输出】
Case 1: 2
Case 2: 1

【限制】
1s

贪心. 其实和【1】非常像，但是和【1】又有本质的不同. 因为【1】是一维的. 例如 (-5,3) 和(-3,5) 如果采用【1】中贪心的策略，则首先是(-1,0)的雷达可以观测到(-5,3)而且最远. 但是(-1,0)无法观测到(-3,5) ，这样导致将建立两座雷达. 【1】的贪心策略本质上需要a被覆盖的话, 则[a,r]之间的点也会都被覆盖，但是这是一维的性质，对于二维是不成立的. 所以【1】的贪心策略用到本题是会WA的. 正确的贪心姿势是什么呢? 对每个海岛进行预处理得到能观测到它们的雷达所在闭区间. 则问题转换为

1
一维直线上有若干区间，问最少取多少个点构成的集合S能使得每个区间和S的交集都不为空?

策略显然也是贪心——首先将区间按照左端点升序排序，则[a0,b0]中显然要取一个点，然后看[a1,b1], 因为a1>=a0, 所以看 a1和b0之间的关系. 如果a1<=b0的话，则不需要增加点的个数. 否则需要增加一个点, 而且这个点是在[a1,b1]中. 然后考察第三个区间[a2, b2], 如果a2>b1的话，显然也是需要增加一个点的，否则的话，因为a2>=a1，则不需要增加点. 直至处理完所有的区间.

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const double eps = 1e-6; // 防止精度丢失
//#define LOCAL

int n,d;

struct Q
{
	double a,b;
	bool operator<(Q o)
	{
		return a<o.a;
	}
}q[1005];

int dis(int x, int y, int a, int b)
{
	return (x-a)*(x-a)+(y-b)*(y-b);
}

bool process(int i, int x, int y) // 预处理海岛 (x,y) 能被观测到的雷达所在闭区间范围
{
	if (y*y>d) // 如果发现海岛离海岸线最近也>d的话,直接返回false
	{
		return false;
	}
	q[i].a = x-sqrt(1.0*d-y*y);
	q[i].b = x+sqrt(1.0*d-y*y); // 此题甚坑~ 雷达安装位置未必是整数格点
	return true;
}

int ks()
{
	int ans = 1;
	double x =q[0].a,y = q[0].b; // [x,y]是当前贪心取点的区间
	for (int i = 1; i<n;i++) // 从第二个区间开始考察
	{
		x = q[i].a;
		if (q[i].a>y+eps) // 如果完全没有交集了
		{
			ans++; // 一定要增加雷达
			y = q[i].b; // 更新y
		}
		else if(q[i].b<=y+eps) // 如果q[i]完全被包含在[x,y]中, 则贪心取点的范围就要缩小
		{
			y = q[i].b;
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	bool flag; // 预处理的过程中有没有返回false? 
	while(scanf("%d%d", &n, &d), n||d)
	{
		flag = false;
		kase++;
		if (d<0) // 此题坑甚多
		{
			printf("Case %d: %d\n", kase, -1);
			flag = true;
		}
		else
		{
			d = d*d;
		}
		for (int i = 0,x,y; i<n;i++)
		{
			scanf("%d%d", &x, &y);
			if (flag) // 属于本样例的数据也要处理完
			{
				continue;
			}
			if (!process(i,x,y))
			{
				printf("Case %d: %d\n", kase, -1);
				flag = true;
			}
		}
		if (flag)
		{
			continue;
		}
		sort(q,q+n);
		printf("Case %d: %d\n",kase, ks());
	}
	return 0;
}

ac情况

Status Accepted
Memory 120kB
Length 1495
Lang C++
Submitted 2019-08-24 14:14:45
Shared
RemoteRunId 20795306

参考

【1】https://yfsyfs.github.io/2019/08/16/poj3069-Saruman-s-Army-贪心/