ACMレーダ設定の問題

Problem Description
海岸線が無線長の直線であると仮定すると、海岸線の片側は海であり、片側は陸地であり、海の中の小さな島ごとに点と見なすことができる.テーマを簡略化するために、私たちはそれを座標軸と見なして、X軸は海岸線で、Y>0の区域は海で、Y<0の区域は陸地で、すべての小さな島はY>0の区域の上の1つの点です.スタッフは海岸線にレーダーを置くつもりで、各レーダーは一定の作用範囲を持っていて、半径dの円です.ある島がレーダーからの距離がdより大きくない場合、島はレーダーで覆うことができる.レーダーの作用半径dと、各島の位置を与え、少なくともどれだけのレーダーがすべての島を覆うことができるかを計算する.
Input
本題には複数のテストデータが含まれています.ファイル終了(EOF)まで処理してください.各テストデータの最初の行には2つの整数N(1<=N<=1000)とdが含まれています.それぞれ島の個数とレーダーの作用範囲dを表しています.次にN行、各行の2つの整数x、yはある島の位置を表す.
Output
各テストデータのセットは、少なくとも必要なレーダーの数を示す整数を出力する.どのようにレーダーを配置しても、すべての島をカバーできない場合は、"-1"(二重引用符を含まない)を出力します.
Sample Input

3 2
1 2
-3 1
2 1
1 2
0 2

Sample Output

2
1

Author
tianzuwei
思考:この問題は最小のレーダー数を求めることにある.私はすべての島の位置を得て、最大x座標と最小y座標を見つけて、それからこれらの点を遍歴して、多くの島を同時に覆う場所を探し始めました.よく考えてみると通じないようだ.あきらめた.ある大物のブログを見てから自分の問題を発見して、私はいつもテーマが求めていることを出発点とするのが好きです.最低レーダーを求めて、私は多くの島をカバーできる場所を探して、すべてカバーしてからでいいです.大物は島を中心に、X軸の上に覆われている区間を見つけ出すと言った.半径r、島の位置(x,y)のように、カバーできる区間は[x-sqrt(r*r-y*y)、x+sqrt(r*r-y*y)]である.次に、得られた区間配列を左境界で小さいものから大きいものに並べ替える.次に、最初の区間の右境界を記号とし、ある区間の左境界が記号より大きい場合、レーダー数に1を加え、記号を二次区間の右境界と更新する.

#include
 
using namespace std;

struct stu
{
	double l,r;
};

bool cmp(struct stu a, struct stu b)
{
    
    return a.l < b.l;
}
struct stu num[1001];

int main()
{
   // freopen("in.txt","r",stdin);
   
    int n, m;
    while(cin >> n >> m)
    {
        int i;
        int x, y;
        int flag = 0;
        if(m <= 0) 
		{
			cout << -1 << endl;
			continue;
		}
        for(i = 0; i < n; i++)
        {
            cin >> x >> y;
            num[i].l = x-sqrt(m*m - y*y);
            num[i].r = x+sqrt(m*m - y*y);
            if(y > m || y < 0) flag = 1;
        }
        if(flag) 
        {
        	cout << -1 << endl;
			continue;
		}
        sort(num,num+n,cmp);
        int cas = 1;
        double xx = num[0].r;
		for(i = 1; i < n; i++)
		{
			if(num[i].l > xx)
			{
		    	xx = num[i].r;
				cas++;
			}
		//	else if(num[i].r < xx)
		//	xx = num[i].r;
		 } 
		 cout << cas << endl;
    }
    fclose(stdin);
    return 0;
}