uva10382专题

uva10382 - Watering Grass(区间覆盖变形)

题目:uva10382 - Watering Grass(区间覆盖变形)   题目大意:要给一片草坪浇水,给定草坪的长度和宽度,给出每个喷头的圆心C和喷水的半径R,问最少要几个喷头可以给整片草坪都浇上水。   解题思路:区间覆盖问题的变形,因为草坪有宽度W,所以这个每个喷头的有效范围是[C- sqrt(R* R - 0.25 * W * W   ,  C + sqrt (R*R - 0.2