题解 UVA1193 【Radar Installation】

是一道比较简单的贪心，主要是对公式的运用。

题意

多组测试数据。

给你n个坐标上的点, n <= 1000。

你可以在x轴上放置雷达,每个雷达的辐射半径都是d。

现在问你辐射到所有的点至少需要几个雷达,如果辐射不到所有的点输出-1。

题解

因为二维的贪心比较困难，所以我们使用圆形的公式即可。用公式转化后，就变成了一道覆盖区间的普通贪心。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define eps 0.0000005
using namespace std;
struct note 
{
	double x;
	double y;
}a[30001];
int n;
double s;
double l,r;
int sum;
bool cmp(note a,note b)
{
	return a.x<b.x;
}
int main()
{
	cin>>n>>s;
	while(n&&s)
	{
		int flag=0;
		for(int i=0;i<n;i++) 
		{
			cin>>l>>r;
			if(abs(r)>s) flag=1;
			a[i].x=l-sqrt(s*s-r*r);
			a[i].y=l+sqrt(s*s-r*r);//公式的运用
		}
		if(flag) //特判
		{
			cout<<"Case "<<++sum<<": -1"<<endl;
			for(int i=0;i<n;i++) a[i].x=a[i].y=0.0;
			scanf("\n%d %lf",&n,&s);
			continue;
		}
		sort(a,a+n,cmp);//开始寻找
		double right=a[0].y;
		int ans=1;
		for(int i=1;i<n;i++)
			if(a[i].x<=right) right=min(right,a[i].y);
			else right=a[i].y,ans++;
		cout<<"Case "<<++sum<<": "<<ans<<endl;
		for(int i=0;i<n;i++) a[i].x=a[i].y=0.0;
		scanf("\n%d %lf",&n,&s);
	}
	return 0;
}