喷水装置（一）（C语言代码）

原题链接：题目6 - ACM在线评测系统

描述

现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入

第一行m表示有m组测试数据
每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出

输出所用装置的个数

样例输入

2
5
2 3.2 4 4.5 6
10
1 2 3 1 2 1.2 3 1.1 1 2

样例输出

2
5

解题思路：为了选择尽量少的喷水装置，首先对其半径进行排序，使用静态链表，表内每个元素用数组下标指向“链表”中随后的元素，输入半径时，采用插入排序，使每个半径从小到大用下标指向链接在一起。随后计算喷水装置半径和草坪宽的一半，能否形成直角三角形的两边，如图所示：如果能覆盖矩形区域，也就能“湿润草坪”。

注意事项：在对象（如喷水装置）总数有限定的前提下，不妨使用有限静态链表；否则还是需要再次开辟空间。

参考代码：

#include<stdio.h>
#include<math.h>
typedef struct z{
	double w;
	int x;
} y;
int main(){
	int m,n,a,b,c;
	double d,e;
	y v[599];//最多599个装置
	scanf("%d",&m);
	while(m--){
		scanf("%d",&n);
		v[0].x=0;
		for(a=1;a<=n;a++){
			scanf("%lf",&v[a].w);
			for(b=0;v[b].x&&v[a].w<v[v[b].x].w;b=v[b].x);
			v[a].x=v[b].x;//找到插入静态链表的位置，下标指向
			v[b].x=a;
		}
		for(e=.0,c=0,b=v[0].x;b&&e<20;b=v[b].x,c++){
			d=pow(v[b].w,2)-1;
			if(d>0)e+=2*sqrt(d);//能找到内接矩形
		}
		printf("%d\n",c);
	}
}