诛仙3二重龙门怎么开:poj1328

先解释下题目。题目的意思是在一个海上有许多小岛，为了能够探测到这些岛，打算在海岸上建立雷达站(海岸是直的)，给出岛的坐标，给出雷达站的覆盖半径，求最少需要多少个雷达站能覆盖所有的小岛。

乍看之下这个题目就是贪心，先算出每个岛在哪个区间范围内建立雷达站能够覆盖到这个岛，排个序，然后每次都取右面坐标就是了，但是这个想法不对，因为总是可以举出反例的（具体的先不谈）。而正确的算法是：要考虑把雷达站放到哪个位置使得包含雷达的区间最多！要不是看其他大牛的blog，我这辈子是够呛能想出来了，呵呵。

写算法的时候要注意，排序完成后，第一个雷达建立在区间的右端，而后一次判断每个区间的左端点，如果在最新建立的雷达右面，那么肯定需要一个雷达，而且也建在区间右端。如果左端点在雷达左面，这个时候要考虑区间的右端在雷达的左面还是右面，如果是右面，那雷达位置就不变，如果在左面，那现在的雷达是覆盖不了的，所以要把雷达放在该区间的右端点！因为这样同时还能覆盖原来的岛，还能覆盖现在的岛！

不多说了，看代码就清楚了

#include
#include

using namespace std;
double pos[1001][2];
struct In
{
 double left,right;
}qujian[1001];

int cmp( const void *a ,const void *b)
{ 
 return (*(In *)a).left >= (*(In *)b).left ? 1 : -1;
}
double wucha = 0.00000001;
int main()
{
 int n,d;
 int total = 0;
 while (cin >> n >> d)
 {
  bool b = true;
  if (n == 0 && d == 0)
   break;
  if (d <= 0)
   b = false;
  int i;
  for (i = 0; i < n; ++i)
   cin >> pos[i][0] >> pos[i][1];
 
  for (i = 0; i < n; ++i)
  {
   double temp = d*d - pos[i][1] * pos[i][1];
   if (temp < 0)
   {
    b = false;
    break;
   }
   else
   {
    qujian[i].left = pos[i][0] - sqrt(temp);
    qujian[i].right = pos[i][0] + sqrt(temp);
   }
  }
  if (b)
  {
   qsort(qujian,n,sizeof(qujian[0]),cmp);
   double radar = qujian[0].right;
   int t = 1;
   for (i = 1; i < n; ++i)
   {
    if (qujian[i].left > radar)
    {
     ++t;
     radar = qujian[i].right;
    }
    else
    {
     if (qujian[i].right < radar)
      radar = qujian[i].right;
    }
   }
   printf("Case %d: %d\n",++total,t);
  }
  else
  {
   printf("Case %d: -1\n" ,++total);
  }

 }
 return 0;
}