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;
}

猜你喜歡