【解题报告】 POJ1328 雷达设备

题目：雷达设备（已翻译）

解题思路：

贪心。

这道题只需要将x轴上方的一些建筑物，利用勾股定理算出x轴上一段能管辖它的区间，所以问题就变成了给定n个区间，在x轴上放置最少的点，使每个区间至少包含一个点，但是，特别地，如果建筑物的纵坐标超出了每个雷达管辖的半径，就直接不会继续下去了，因为不管怎么样，那个建筑物都无法被管辖，所以我们只需要每个建筑物算出来的区间的右端点进行排序，然后设置一个数组vis，来记录每个建筑物是否被管辖到，然后就ok了

AC代码

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1005;
int n,d;
int ans;
bool vis[maxn];
struct sec
{
	double l;
	double r;
}b[maxn];
bool cmp(sec p,sec q)
{
	return p.r<q.r;
}
int main()
{
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		y=abs(y);
		if(y>d)
		{
			cout<<"-1"<<endl;
			return 0;
		}
		b[i].l=x-sqrt(d*d-y*y);
		b[i].r=x+sqrt(d*d-y*y);
		vis[i]=false;
	}
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			ans++;
			vis[i]=true;
			for(int j=i+1;j<=n;j++)
			{
				if(b[j].l<b[i].r)
				vis[j]=true;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}