POJ 1328 Radar Installation 题解 | 宁心勉学，慎思笃行

解决方法并不难，贪心算法。对于每一个岛屿，以其坐标为圆心，d为半径作圆，两个交点就是可以安放雷达的范围。取出所有范围，合并可以共用的范围，即是答案。

这道题目给了我几点启发。

一定要注意贪心算法的正确性和完整性。
对问题要考虑全面。比如d<0的情况。
stdlib 中的qsort函数中，compare调用一定要返回 int 类型。因此，返回的时候千万不要直接返回double，否则这个double被自动转换过之后就不一定对了。这道题中，return gety0point(zb1) < gety0point(zb2)?-1:1;必须注意。如果换成直接返回他们的差值，就可能出错。
该用double的地方就用double，不要习惯性的使用int。

/*
 *	Radar Installation
 *	URL: http://poj.org/problem?id=1328
 *	Author: Ceeji Cheng
 *	Type: 貪心
 *	Status: Solved
 *	Visit http://ceeji.net/ for more information.
 *	2010-11-30
 *
 */
 
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
 
using namespace std;
 
#define maxn 1000
#define dis(x1,y1,x2,y2) pow((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2),0.5)
 
struct xy
{
	int x, y;
};
 
int n, d;
xy zb[maxn];
bool cannot = false;
 
inline double gety0point(const xy* zb)
{
	int f = d*d - (zb->y)*(zb->y);
	if (f < 0)
		return 9999999;
	return pow(static_cast<double>(f), 0.5) + zb->x;
}
 
inline double gety0point_l(const xy* zb)
{
	int f = d*d - (zb->y)*(zb->y);
	if (f < 0)
		return 9999999;
	return -pow(static_cast<double>(f), 0.5) + zb->x;
}
 
int cmp(const void* v1, const void* v2)
{
	const xy* zb1 = static_cast<const xy*>(v1);
	const xy* zb2 = static_cast<const xy*>(v2);
	int i = gety0point(zb1), j = gety0point(zb2);
	if (i == 9999999 || j == 9999999)
		cannot = true;
	return gety0point(zb1) < gety0point(zb2)?-1:1;
}
 
int main(int argc, char const* argv[])
{
	int m = 0;
	while (cin >> n >> d)
	{
		++m;
		if (n == 0 && d == 0)
		{
			return 0;
		}
		cannot = false;
		for (int i = 0; i < n; ++i)
		{
			cin >> zb[i].x >> zb[i].y;
			if (zb[i].y < 0)
				cannot = true;
			if (zb[i].y > d)
				cannot = true;
		}
		if (d < 0 || cannot)
		{
			cout << "Case " << m << ": -1" << endl;
			continue;
		}
		qsort(zb, n, sizeof(xy), cmp);
		if (cannot)
		{
			cout << "Case " << m << ": -1" << endl;
		}
		else
		{
			int need = 1;
			double l = gety0point_l(&zb[0]), r = gety0point(&zb[0]), tmpl;
			for (int i = 1; i < n; ++i)
			{
				tmpl = gety0point_l(&zb[i]);
				if (tmpl > r)
				{
					l = tmpl;
					r = gety0point(&zb[i]);
					++need;
				}
			}
			cout << "Case " << m << ": " << need << endl;
		}
	}
	return 0;
}

猜你喜欢