该题题意是为了求出能够覆盖所有岛屿的最小雷达数目，而由题目我们可以求出每个岛屿雷达能覆盖的区间，该区间在岛屿横坐标两边对称的长度[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)];然后我们对岛屿按左区间从小到大排序，说到这里，我们脑海中就浮现出来了贪心的经典活动安排问题，把这些区间看成一个活动的【开始时间--结束时间】，要求我们尽可能地选择一个方案最多的活动，前提是活动要兼容，即时间不冲突，而所求的最多方案是就是我们要求的最小雷达数目；例如这组数据；
3 2
0 0
1 2
4 0
我们可以算出时间区间并排序后有：1【-2，2】2【1，1】，3【2，6】；我们用一个变量currentRight记录当前的右区间，首先currentRight=2;因为区间2的开始区间在区间1的右区间的里面，因此1.2区间有交集，这时候我们不给2增加雷达，1，2交集后，我们要更新因为currentRight=2>区间2的1;所以currentRight=1;对于区间3，因为currentRight=1<2,不想交，因为要增加一个雷达数，所以该组数据为2；即可求解。还没有的兄弟们，加油哦~


PS：题目中数据有出现d<=0,直接输出Case #: -1即可，如果还一直卡住过不了的可以去参考我的代码http://lovekid1987.blog.163.com/blog/static/11518421020093172218978/

• 感谢楼主提醒~~ (0) lanseniao 2009-07-17 21:51:33
• Re:关于1328的解题思路~~ (650) sdie2008140224 2010-03-30 19:55:45
• Re:关于1328的解题思路~~ (23) csulk 2010-07-15 16:14:23
• Re:关于1328的解题思路~~ (10) kaitian5201314 2010-09-07 21:20:00
  • Re:关于1328的解题思路~~ (13) duyimin 2011-04-07 19:21:35