B. 【例题2】雷达装置

内存限制：64 MiB

时间限制：1000 ms

标准输入输出

题目类型：传统

评测方式：文本比较

题目描述

有个建筑物，第个建筑物在笛卡尔坐标系上的坐标为，你需要在轴上安装一些雷达，每个雷达的侦察半径均为，要求每个建筑物都至少被一个雷达侦测到，求最少要安装几个雷达。

输入格式

第一行两个正整数。

接下来行，第行两个整数。

输出格式

输出一行表示答案，若没有解决方案，则答案为。

样例

样例输入

3 2

1 2

-3 1

2 1

样例输出

数据范围与提示

对于 $\%100$ 的数据，有 $1\leq N\leq10^3$ 。

思路

先画个图感性理解一下：

能检测到点（x,y）的雷达只能在圆圈内，而在x轴内的雷达就只在 [l,r] 区间内了。

由勾股定理得：

d^2=(x-l)^2+y^2=(r-x)^2+y^2

所以

\sqrt{d^2-y^2}=x-l=r-x

所以

l=x-\sqrt{d^2-y^2}，r=x+\sqrt{d^2-y^2}

所以我们就能求出每个点对应的区间，

然后问题就变成在n个区间里放最少的点，使得每个区间里都有点。

贪心策略为：

将区间按右端点从小到大排序，

然后枚举每个区间，若这个区间里有雷达（即最近放的雷达在左端点的右边），则不管它。

否则，放一个雷达在这个区间的右端点。

证明省略······

代码

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;ll n,ans;double x,y,d,t;struct node{
   	double l,r;} a[1001];ll cmp(node x,node y){
   	return x.r
      
       >n>>d;	for(int i=1; i<=n; i++)	{
   		cin>>x>>y;		x+=10000001;//将可能的负数变成正数		if(d
       
        t)		{
   			t=a[i].r;			ans++;//得加一个雷达		}	}	cout<