POJ 1328 贪心-蒲公英云

POJ 1328 贪心

算法：

1.求出覆盖该岛的圆得区间, 將问题转换为求过出最少得点，保证每个区间至少有一个点。

2.按区间的左端排序

3.更新rad

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct node
{
  double x, y; 
  bool operator < (const node& A) const
  {
     return x < A.x;     
  }
}px[10000], seg[10000];
double Circle1( double x, double y, double R)
{
   return x + sqrt( R * R - y * y );      
}
double Circle2( double x, double y, double R)
{
   return x - sqrt( R * R - y * y );      
}
int main( )
{
   int n, d, ans = 1;
   while( scanf("%d%d", &n, &d), n + d)
   {  
      int t = 0, num = 0;
      double ymax = 0;
      for( int i = 0; i < n; i++)
      {
        scanf("%lf%lf",&px[i].x, &px[i].y);
        if( px[i].y > ymax )
            ymax =  px[i].y;
      }
      if( ymax > d  )
      {
         printf("Case %d: %d\n", ans++, -1);
         continue;    
      }
      //求出圆心区间【X，Y】
      for( int i = 0; i < n; i++)
      {
         double x1 = px[i].x;
         double y1 = px[i].y;
         double Y = Circle1( x1, y1, d);
         double X = Circle2( x1, y1, d);
         seg[t].x = X;
         seg[t].y = Y;
         t++;
      }
      sort(seg, seg + t );
      double rad = seg[0].y;
      num = 1;
      for( int i = 1; i < t; i++)
      {
          if( rad - seg[i].x > 10e-7 ) 
          {
             if( seg[i].y - rad < 10e-7 )
         rad = seg[i].y; 
          }
          else if( seg[i].x - rad > 10e-7 )
          {
              rad = seg[i].y;
              num++;
          }
      }
      printf("Case %d: %d\n", ans++, num);  
   }
}