基站建设问题

一起来看看这题，题意：在二维坐标中，有n个点，要求在x轴上某点为圆心，d为半径，能覆盖这些点，求需要这样的几个圆。如果无法完全覆盖输出-1

思路：

       我们可以逆向思考，如果以二维坐标上的点P（x,y）为圆心，d为半径，则有两个点经过x轴，那两个点即为x轴上能覆盖到P的最近点和最远点，如图

在Xmin和Xmax之间的任意x为圆心肯定都能覆盖到P点。那问题就转换成了任意Pi的Xmin和Xmax比较的问题。

（1）判断这些点y是否在d的范围内，如果超出肯定不能 完全覆盖

（2）求出这些点的的Xmin和Xmax,然后以Xmin从小到大进行排序

（3）如果P1.Xmax<P2.Xmin ,代表两点不能在一个圆内覆盖，需要再画一个圆（再建立一个基站）ans++

         如果P1.Xmax>P2.max,代表两点能在一个圆内覆盖，但是最远距离 Xmax更新了，变成了P2.Xmax

就这样，这题就差不多能够解决了，接下来不懂的看看的代码，仔细想想就能想清楚了。

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAX 1001
struct Tpoint
{
    int x;
    int y;
};
struct Tseg
{
    double tmin;
    double tmax;
};
Tpoint point[MAX];
Tseg seg[MAX];

void Input(int n);
bool judge(int n,int d);
void vsort(int n);
bool vcmp(const Tseg &a,const Tseg &b);
int getNum(int n);
void vout(int nc,int out);

int main()
{
    int ncase=1,nNum,nDis;
    while(cin>>nNum>>nDis)
    {
        int ans;
        if(nNum==0&&nDis==0)
        {
            return 0;
        }
        Input(nNum); //输入点
        if(judge(nNum,nDis)==true)
        {
            vsort(nNum);
            ans=getNum(nNum); //得到基站数
        }
        else
        {
            ans=-1; //不符合输入-1
        }
        vout(ncase,ans);//输出
        ncase++;
    }
    return 0;
}

void Input(int n)
{
     int i;
     for(i=1;i<=n;i++)
     {
         cin>>point[i].x>>point[i].y;
     }
}
bool judge(int n,int d)
{
   int i;
   for(i=1;i<=n;i++)
   {
       if(point[i].y>d)
       {
           return false;
       }
       seg[i].tmin=point[i].x-sqrt(1.0*d*d-1.0*point[i].y*point[i].y);
       seg[i].tmax=point[i].x+sqrt(1.0*d*d-1.0*point[i].y*point[i].y);
   }
   return true;
}
void vsort(int n)
{
   sort(&seg[1],&seg[n+1],vcmp);
}
bool vcmp(const Tseg &a,const Tseg &b)
{
     return a.tmin<b.tmin;
}
int getNum(int n)
{
    int ret=1;
    int temp=seg[1].tmax;
    int i;
    for(i=2;i<=n;i++)
    {
        if(temp<seg[i].tmin)
        {
            ret++;
            temp=seg[i].tmax;
        }
        else if(temp>seg[i].tmax)
        {
            temp=seg[i].tmax;
        }
    }
    return ret;
}
void vout(int nc,int out)
{
     cout<<"Case "<<nc<<": "<<out<<endl;
}