M01328 Radar Installation

思路：

• 若 $\mathrm{\exists }1\le i\le n,\text{s.t. }{y}_i>d$，显然无解；否则，$\mathrm{\forall }1\le i\le n$，令 $r_i=\sqrt{d^2-y_i^2}$，我们要求 $[x_i-r_i,x_i+r_i]$ 中至少存在一个雷达。
• 因此问题抽象为：给定数轴上若干线段 $[L_i,R_i]$，要求在数轴上选出尽可能少的点，使得每一条线段中都至少含有一个点。
• 考虑按 $R_i$ 将线段升序排序，记录当前选的最靠右的点的位置 $t$，若 $t<L_i$ 则在 $R_i$ 处新选一个点。
• 时间复杂度为 $O(\sum n\log n)$。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

struct Requirement {
	double l;
	double r;
};

const double eps = 1e-9;
int x[1001], y[1001];
Requirement req[1001];

bool operator <(const Requirement a, const Requirement b){
	return a.r < b.r;
}

bool myless(double a, double b){
	return fabs(a - b) > eps && a < b;
}

bool solve(int cas){
	int n, d;
	cin >> n >> d;
	if (n == 0 && d == 0) return false;
	bool flag = true;
	for (int i = 1; i <= n; i++){
		cin >> x[i] >> y[i];
		if (y[i] > d) flag = false;
	}
	if (!flag){
		cout << "Case " << cas << ": " << -1 << endl;
		return true;
	}
	int ans = 0;
	double lst = -1e10;
	for (int i = 1; i <= n; i++){
		double r = sqrt((ll)d * d - (ll)y[i] * y[i]);
		req[i].l = x[i] - r;
		req[i].r = x[i] + r;
	}
	sort(req + 1, req + n + 1);
	for (int i = 1; i <= n; i++){
		if (myless(lst, req[i].l)){
			lst = req[i].r;
			ans++;
		}
	}
	cout << "Case " << cas << ": " << ans << endl;
	return true;
}

int main(){
	for (int i = 1; solve(i); i++) ;
	return 0;
}

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

struct loc{
 int x;
 int y;
};
struct range{
 float l;
 float r;
};
range f(loc a,int d){
 float w=sqrt(d*d-a.y*a.y);
 return {a.x-w, a.x+w};
}
bool cmp(range a,range b){
 return a.r<b.r;
}
int main(){
 int count=0;
 bool noans=0;
 while(true){
     count++;
     int n,d;
     cin>>n>>d;
     if(n==0&&d==0) {break;}
     vector<loc> locs(n);
     vector<range> ranges(n);
     for(int i=0;i<n;i++){
         cin>>locs[i].x>>locs[i].y;
     }
     for(int i=0;i<n;i++){
         if(locs[i].y>d){
             cout<<"Case "<<count<<": "<<-1<<'\n';
             noans=1;
             break;
         }
     }
     //就只是因为这两行代码交换了位置，改了半天的错。。。

     if(noans==1){noans=0;continue;}
     if(n==1) {cout<<"Case "<<count<<": "<<1<<'\n';continue;}

     //就只是因为这两行代码交换了位置，改了半天的错。。。
     for(int i=0;i<n;i++){
         ranges[i]=f(locs[i], d);
     }
     sort(ranges.begin(),ranges.end(),cmp);
     int ans=1;
     float rad=ranges[0].r;
     for(int i=1;i<n;i++){
         if(rad<ranges[i].l){
             rad=ranges[i].r;
             ans++;
         }
     }
     cout<<"Case "<<count<<": "<<ans<<'\n';
 }
 return 0;
}