# 雷达 - 第二课：贪心算法 - 区间覆盖 / 字典序 - 2020 最新版提高组初级课程

题目链接

# 思路

用勾股定理求出区间

转化成区间覆盖问题

# 代码

	#include <bits/stdc++.h>
	using namespace std;

	struct jgt
	{
	int x,y;
	double z;
	} a[100010];

	bool cmp(jgt a,jgt b) {
	return a.z<b.z;
	}

	int n,d,ans=1;
	int main()
	{
	cin>>n>>d;
	bool flag=false;
	for(int i=1;i<=n;i++) {
	cin>>a[i].x>>a[i].y;
	//cout<<a[i].x<<" "<<a[i].y<<endl;
	if(a[i].y>d\|\|a[i].y<(-1*d)) {
	flag=true;
	}
	a[i].z=a[i].x+sqrt(dd-a[i].ya[i].y);
	}
	if(flag) {
	cout<<-1<<"\n";
	return 0;
	}
	sort(a+1,a+n+1,cmp);
	double tmp=a[1].z;
	for(int i=2;i<=n;i++) {
	if((a[i].x-tmp)(a[i].x-tmp)+a[i].ya[i].y>d*d) {
	ans++;
	tmp=a[i].z;
	}
	}
	cout<<ans<<"\n";
	return 0;
	}