[C++]Radar Installation POJ - 1328

Radar Installation:
将一条海岸线看成X轴，X轴上面是大海，海上有若干岛屿，给出雷达的覆盖半径和岛屿的位置，要求在海岸线上建雷达，在雷达能够覆盖全部岛屿情况下，求雷达的最少使用量。

输入格式：
n (1<=n<=1000) and d
This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.
The input is terminated by a line containing pair of zeros
输出格式：
For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. “-1” installation means no solution for that case.

输入：
3 2
1 2
-3 1
2 1

1 2
0 2

0 0
输出：
Case 1: 2
Case 2: 1

解题分析：
每个岛屿在海岸线能被探测到的位置都有一个区间，把能探测到岛屿的每个区间求出来，此时就变成了区间问题，问有多少个独立的区间块。

AC代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;

typedef pair<double, double> P;
double n, d;
struct ST{
	double left;
	double right;
};

int cmp(P a, P b){
	return a.first < b.first;
}

int main(){
	int Case = 1;
	while(cin>>n>>d){
		if(n == 0 && d == 0)
			break;
		ST st[1010];
		vector<P> vec;
		int flag = 0;
		for(int i = 0; i<n; i++){
			cin>>st[i].left>>st[i].right;
			if(fabs(st[i].right) > d)
				flag = 1;
			double left = st[i].left*1.0 - sqrt(d*d - st[i].right*st[i].right);
			double right = st[i].left*1.0 + sqrt(d*d - st[i].right*st[i].right);
//			 cout<<left<<" "<<right<<endl;
			vec.push_back(P(left, right));
		}
		if(flag){
			cout<<"Case "<<Case++<<": "<<-1<<endl;
			continue;
		}
		sort(vec.begin(), vec.end(), cmp);
		int res = 1;
		double end = vec[0].second;
		for(int i = 1; i<vec.size(); i++){
			if(vec[i].second < end){
				end = vec[i].second;
			}
			else if(vec[i].first > end){
				end = vec[i].second;
				res++;
			}
		}
		
		cout<<"Case "<<Case++<<": "<<res<<endl;
	}
	
	return 0;
} 

最后

以上就是懦弱蜜蜂为你收集整理的[C++]Radar Installation--POJ1328[C++]Radar Installation POJ - 1328的全部内容，希望文章能够帮你解决[C++]Radar Installation--POJ1328[C++]Radar Installation POJ - 1328所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。