HAOI2014遥感监测题解

发表于 | 分类于 | | 浏览 次
字数统计: 1,038 个 | 阅读时长 ≈ 4 分

[HAOI2014]遥感监测

题目描述

外星人指的是地球以外的智慧生命。外星人长的是不是与地球上的人一样并不重要，但起码应该符合我们目前对生命基本形式的认识。比如，我们所知的任何生命都离不开液态水，并且都是基于化学元素碳（C）的有机分子组合成的复杂有机体。

ZDM实验室的天文学家们已经执著地观测ZDM-99星球十多年了，这个被称为“战神”的红色星球让他如此着迷。在过去的十多年中，他经常有一些令人激动的发现。ZDM-99星球表面有着明显的明暗变化。对这些明暗区域，天文学家们已经细致地研究了很多年，并且绘制出了较为详尽的地图，那些暗区是陆地，而亮区则是湖泊和海洋。他们一直坚信有水的地方，一定有生命的痕迹。

这天晚上的观测条件实在是空前的好，ZDM-99星球也十分明亮，不时呈现出若干个激光点，天文学家们推定这些激光点极有可能存在地球以外的智慧生命。遗憾的是仅持续很短的一段时间，这些激光点就消失了。

ZDM实验室的射电望远镜观测的区域有限，只可以遥感检测到一个半径为R的圆形区域。为了能同时能检测到所有的激光点，ZDM实验室需要要在一个水平的直线上尽快地安装多个的射电望远镜来。

不妨设，这条安放射电望远镜的水平直线为X轴，ZDM-99星球激光点就处在P1（x1,y1）P2(x2,y2) ，…… ，Pn(xn,yn)。（忽略Z坐标）

ZDM实验室的天文学家们想知道，至少需要安装多少个射电望远镜才能检测到所有激光点。

输入格式

第1行: N R 分别表示激光点的个数和射电望远镜能检测到的半径
第2~N+1行： Xi Yi 表示 激光点的坐标位置

输出格式

输出一行： 最少需要安装的射电望远镜数。

样例输入

3 2
1 2
-3 1
2 1

样例输出

2

约束条件

1≤R≤50 1≤N≤100 -1000≤ Xi Yi ≤ 1000 | Yi | ≤ R
N，R, Xi Yi都是整数。数据之间有一个空格。

题解

大概是个贪心，找出能保证包住最靠左的激光点的最靠右边的x轴坐标，但是枚举所以点时间复杂度明显太高，所以换一种思路，使用结构体处理出每个激光点所能被包住的可以作为望远镜的可行区间


处理方法很简单

1
2
3
4
5
for(int i=1;i<=n;i++){
	double fan=sqrt(pow(r,2)-pow(p[i].y,2));//pow()是n次方函数pow(x,n)表示x的n次方
	p[i].l=p[i].x-fan;
	p[i].r=p[i].x+fan;
}

然后对处理后的区间按照右端点进行排序(请同学们自主思考：为什么是右端点)然后进行统计

1
2
3
4
5
6
7
8
9
10
int k=1, ans=1;
for(int i=2;i<=n;i++){
	if(p[i].l<=p[k].r){//p[k].r点可观测到点i
		continue;
	}
	else {//更新k
		k=i;
		ans++;
	}
}

最后放一下全部代码

代码实现

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int ans,r,n;
inline int read(){
	int k=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())k=k*10+c-'0';
	return k*f;
}
class mp{
public:
	int x;
	int y;
	double l;
	double r;
}p[2333];
bool cmp(mp a,mp b){
	return a.r<b.r;
}
int main(){
	freopen("ha14a.in","r",stdin);
	freopen("ha14a.out","w",stdout);
	n=read();
	r=read();
	for(int i=1;i<=n;i++){
		p[i].x=read();
		p[i].y=read();
		if(abs(p[i].y)>r){
			cout<<-1;
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		double fan=sqrt(pow(r,2)-pow(p[i].y,2));
		p[i].l=p[i].x-fan;
		p[i].r=p[i].x+fan;
	}
	sort(p+1,p+1+n,cmp);
	int k=1;
	ans=1;
	for(int i=2;i<=n;i++){
		if(p[i].l<=p[k].r){
			continue;
		}
		else {
			k=i;
			ans++;
		}
	}
	printf("%d",ans);
	return 0;
}