POJ 1328 贪心

ゞ浴缸里的玫瑰 2021-10-15 11:51 196阅读 0赞

算法：

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

2.按区间的左端排序

3.更新rad

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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);  
    
       }
    
        
    
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/07/09/2582315.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211015/7cb86ab03bf048128b94ade714387eca.png