欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1328 Radar Installation(贪心)

程序员文章站 2022-03-26 14:06:21
...

POJ 1328 Radar Installation(贪心)
题目链接:http://poj.org/problem?id=1328
题意:平面直角坐标系上有n个点,求在x轴上找尽量少的点,以这些点为圆心画一个半径为d的圆,使得给定的点都在画出来的圆里。如果不能输出-1。
solution:围绕点画圆、将圆与x轴相交的区间都记录下来、在对这些区间利用贪心法、找出建雷达站的最少个数!

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

bool cmp(pair<double, double> &a, pair<double, double> &b)
{
	if (a.second != b.second)return a.second < b.second;
	return a.first > b.first;
}

int main()
{
	int n, d, cas = 0;
	while (cin >> n >> d){
		if (!n && !d)return 0;
		bool flag = true;
		double x, y;
		vector<pair<double, double> > vec;
		for (int i = 0; i < n; ++i){
			scanf("%lf%lf", &x, &y);
			if (y > d)flag = false;
			else vec.push_back(make_pair(x - sqrt(d * d - y * y), x + sqrt(d * d - y * y)));
		}
		sort(vec.begin(), vec.end(), cmp);
		if (!flag)printf("Case %d: -1\n", ++cas);
		else {
			double end = vec[0].second, r;
			int cnt = 1;
			for (int i = 1; i < n; ++i)if (end < vec[i].first){
				++cnt;
				end = vec[i].second;
			}
			printf("Case %d: %d\n", ++cas, cnt);
		}
	}
}