南阳市ACM12-喷水装置（二）

南阳ACM12-喷水装置（二）
/*
 喷水装置（二）
 时间限制：3000MS | 内存限制：65535KB 难度：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
 
 样例输入
 2
 2 8 6
 1 1
 4 5
 2 10 6
 4 5
 6 5
 样例输出
 1
 2
 */

import java.io.BufferedInputStream;
import java.util.Scanner;
import java.math.*;


public class Main {
public static void main(String[] args)
{
int n;
Scanner cin = new Scanner(new BufferedInputStream(System.in));

n = cin.nextInt();
while ((n--) != 0)
{
int i, j;
int[][] pData;
double[][] pOverScale;
int nData, w, h;

i = j = nData = w = h = 0;
nData = cin.nextInt(); //喷水装置的个数
w = cin.nextInt(); //草坪的宽
h = cin.nextInt(); //草坪的高
pData = new int[nData][2]; //存放喷水装置
pOverScale = new double[nData][2]; //可以覆盖的范围

for (i = 0; i < nData; ++i)//按受每个喷水装置的参数
{
double length = 0.0;

pData[i][0] = cin.nextInt(); //中心点横坐标
pData[i][1] = cin.nextInt(); //半径
if (pData[i][1] <= h/2) //此喷水装置不能覆盖任何区域，
{
length = 0.0;
pOverScale[i][0] = pOverScale[i][1] = 0.0;
}
else
{
length = Math.sqrt(pData[i][1]*pData[i][1] - (h/2.0)*(h/2.0));

// System.out.println("length = "+length);
if ((pData[i][0] - length) <= 0)
{
pOverScale[i][0] = 0.0;
}
else
{
pOverScale[i][0] = pData[i][0] - length;
}

if ((pData[i][0] + length) >= w)
{
pOverScale[i][1] = w;
}
else
{
pOverScale[i][1] = pData[i][0] + length;
}
}
}

// for (i = 0; i < nData; ++i)
// {
// System.out.println(pOverScale[i][0]+"  "+pOverScale[i][1]);
// }
//查找使用最少装置个数的方法
//首先对该范围的下限进行排序
for (i = 0; i < nData-1; ++i)
{
for (j = nData-i-1; j > 0; --j)
{
if (pOverScale[j][0] < pOverScale[j-1][0])
{
double temp;
temp = pOverScale[j][0];
pOverScale[j][0] = pOverScale[j-1][0];
pOverScale[j-1][0] = temp;

temp = pOverScale[j][1];
pOverScale[j][1] = pOverScale[j-1][1];
pOverScale[j-1][1] = temp;
}
}
}

int nCount = 0; //所使用的最少装置数
double scale = 0.0;
int flag = 0;
int flagOfIndex = 0;
double flagOfMaxLength = 0.0;
for (j = 0; j < nData; ++j)
{
flagOfMaxLength = 0.0;
flag = 0;
for (i = 0; i < nData; ++i)
{
if ((pOverScale[i][0] <= scale) && (pOverScale[i][1] >= scale))
{
if (pOverScale[i][1] - scale > flagOfMaxLength)
{
flagOfMaxLength = pOverScale[i][1] - scale;
flagOfIndex = i;
flag = 1;
}
}
}
if (flag == 1)
{
scale = pOverScale[flagOfIndex][1];
// System.out.println(scale);
nCount++;
}
if (scale >= w)
{
System.out.println(nCount);
break;
}
}
if (j == nData)
{
System.out.println(0);
}
}
}
}