Radar Installation (贪心)

Radar Installation (贪心)

传送门

思路：一开始没看到雷达只能放在$x$轴上，这样就可以转换为区间覆盖问题，预处理出每个岛屿雷达可以放置的区间，然后贪心每次选取区间的最右端，如果当前区间的左端大于它，则$sum++$，更新雷达位置当前区间的右端。

时间复杂度：$O(nlogn)$

#include<iostream>
#include<vector>
#include<algorithm> 
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
struct node{
	double l,r;
	bool operator<(const node& no)const{
		return r<no.r;
	} 
};
int n,d;
vector<node>ans;
void f(int x,int y){
	if(y>d) return;
	double dis=sqrt(d*d-y*y);
	ans.pb({x-dis,x+dis});
}
int main(){
	int kase=0;
	while(~scanf("%d%d",&n,&d)&&(n||d)){
	for(int i=0,x,y;i<n;i++){
		scanf("%d%d",&x,&y);f(x,y);
	}
	if(ans.size()!=n){
		printf("Case %d: -1\n",++kase); 
		ans.clear();
		continue;
	}
	sort(ans.begin(),ans.end());
	int s=1,id=0;
	for(int i=1;i<n;i++)
		if(ans[i].l>ans[id].r) s++,id=i;
	printf("Case %d: %d\n",++kase,s); 
	ans.clear(); 
	}
	return 0;
}