喷水装置（二）
时间限制：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
3
4
5
6
7
| 2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
|
样例输出
这个题和上一题，差不多，有所拓展。虽说代码AC了，但是发现里面还是有点下问题，测试数据太水了。而且排序是没有必要的，懒得改了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| import java.util.Scanner;
public class T3喷水装置2 {
static int w,h,ans;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] out=new int[n];
for (int i = 0; i < out.length; i++) {
int t=sc.nextInt();
w=sc.nextInt();
h=sc.nextInt();
double[][] data=new double[t][2];
for (int j = 0; j < data.length; j++) {
data[j][0]=sc.nextDouble();
data[j][1]=sc.nextDouble();
}
out[i]=getNum(data,w,h);
}
for (int i = 0; i < out.length; i++) {
System.out.println(out[i]);
}
}
}
private static int getNum(double[][] data, int w, int h) {
data=getSort(data);
double x=0,l=0,r=w;
ans=1;
if(data[0][1]*2<h) return 0;
x=Math.pow(data[0][1]*data[0][1]-(h/2)*(h/2),0.5);
r=data[0][0]-x;
l=data[0][0]+x;
while(l<w||r>0){
if(l<w){
l=getl(l,data);
ans++;
}
if(r>0){
r=getr(r,data);
ans++;
}
if(ans>data.length) return 0;
}
return ans;
}
//向右移动
private static double getl(double l, double[][] data) {
double max=0;
for (int i = 0; i < data.length; i++) {
if(data[i][1]*2>h){
double d=Math.pow(data[i][1]*data[i][1]-(h/2)*(h/2),0.5);
if(l<data[i][0]+d){
if(max<data[i][0]+d){
max=data[i][0]+d;
}
}
}
}
return max;
}
//向右移动
private static double getr(double r, double[][] data) {
double min=r;
for (int i = 0; i < data.length; i++) {
if(data[i][1]*2>h){
double d=Math.pow(data[i][1]*data[i][1]-(h/2)*(h/2),0.5);
if(r>data[i][0]-d){
if(min>data[i][0]-d){
min=data[i][0]-d;
}
}
}
}
return min;
}
private static double[][] getSort(double[][] data) {
for (int i = 0; i < data.length; i++) {
for (int j = i+1; j < data.length; j++) {
if(data[i][1]<data[j][1]){
double t1=data[i][0];
data[i][0]=data[j][0];
data[j][0]=t1;
double t2=data[i][1];
data[i][1]=data[j][1];
data[j][1]=t2;
}
}
}
return data;
}
}
|