喷水装置（二）-区间贪心

题目是这样的：

时间限制：3000 ms | 内存限制：65535 KB

难度：4

描述: 有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入

第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出

每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入

样例输出

1
2
解题思想：
1.输入的每个数，其中有效部分是与边相切的弦，把它看成一个区间。
2，按区间的左边大小，从小到大排序。
3.特殊情况：第一个的左边位置大于0，此时可以输出0，并结束
4.最主要的部分结合代码解析：

具体的代码实现如下：
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Water
{
   double l;
   double r;
}
class cmp implements Comparator<Water>
{
   public int compare(Water a,Water b)
   {
       if(a.l > b.l)
       {
           return 1;
       }
       else if(a.l == b.l)
       {
           if(a.r > b.r)
           {
               return 1;
           }
           else if(a.r == b.r)
           {
               return 0;
           }
           else
           {
               return -1;
           }
       }
       else
       {
           return -1;
       }
   }
}
public class Main
{
   static final int MAX = 10005;
   static Water wa[] = new Water[MAX];
   public static void main(String []args)
   {
       Scanner cin = new Scanner(System.in);
       int N = cin.nextInt();
       for(int i = 0 ; i < N ; i++)
       {
           int n,w,h;
           n = cin.nextInt();
           w = cin.nextInt();
           h = cin.nextInt();
           for(int j = 0 ; j < n ; j++)
           {
               wa[j] = new Water();
               int x,r;
               x = cin.nextInt();
               r = cin.nextInt();
               if(2*r <= h)
               {
                   wa[j].l = 0.0;
                   wa[j].r = 0.0;
                   continue;
               }
               double s = Math.sqrt((r*r*1.0-h*h*1.0/4));
               wa[j].l = x*1.0-s;
               wa[j].r = x*1.0+s;
           }
           Arrays.sort(wa,0,n,new cmp());
           if(wa[0].l > 0)
           {
               System.out.print(0 + " ");
               continue;
           }
           double p = 0.0;//刚开始是0
           int cnt = 0;//计数
           int q = 0;//下面for循环的起点
           while(true)
           {
               double s = 0.0;//判断是否存在的，以及离得最远的区间
               for(int j = q ; j < n && wa[j].l <= p; j++)
               {
                   if(wa[j].r - p > s)
                   {
                       s = wa[j].r-p;
                       q = j;
                   }
               }
               if(s != 0)
               {
                   cnt++;
                   p += s;
                   q++;
               }
               else
               {
                   break;
               }
           }
           if(p >= w)
           {
               System.out.print(cnt + " ");
           }
           else
           {
               System.out.print(0 + " ");
           }
       }
   }
}