辗转反侧已经有两个星期了，最终还是被解决了，但是整个路径却是很曲折的。
看了这道题，研究之后，写了一个算法，结果以超时而告终。于是乎看一下有没有人
留下些只言片语，很不幸没有，google和百度都被我点烂了，关于这个题的信息
太少了。
         为什么没有人愿意留点信息呢？

于是我看了下，通过的人的情况，结果人家的要不就是不花时间，要不就是花很少的
时间，内存占用不多。于是我推测我的算法太低效了。
  花了很多时间想另一个高效的算法，结果以失败而告终，没有找到这样的一个高效
算法，最后只能回到原来的那个算法。
  对原来的算法之所以超时，是因为滥用了三角函数，三角函数计算的太慢了，而算法
本身是没有问题的。

下面说下算法的流程：
1.以球的位置为中心，重新计算所有坐标值。
2.每一个目标以矩形区域的四边为对称轴，得出其他的四个目标，即每一个坐标会生成
  四个新的，包括自己一共有5个。题中n最大为100，那生成之后，最大的目标为500，
  那么，最大的点数为2000.为了满足第三步，可以考虑将跨越x轴的目标以x轴划分为
  两个目标，点的数量将增加（当然，也许你有更好的方式）。
3.对所有的点按极角360度排序。注意跨越x轴负半轴的目标。（因为我使用了atan2函数）
4.然后依次扫描点（从-180度到+180度）：
   4.1以第一个点s开始，与s相连的间隔最远的点记为v。
   4.2如果s到v之间的点i的最远间隔点j为v之后的点，则更新v为j,直到扫描完s和v之
      间所有点.将角<s,v>加到答案angle中。
   4.3以v后一个点为新的s重复4.1,4.2直到所有点扫描完。
5.输出(angle/2pi * 100)%

需要注意的几个点：
1.如果使用atan2比较两个点的大小，（从-180度到+180度），将耗费大量的时间，从而导致
  超时。所以需要改用其他的方式比较两个点的大小，我改用了叉积，叉积 a x b判断的是b
  在a的左边还是右边。应该所有的点都在180度范围内（我在程序中，将其所有点分为了两部分
  x轴上方，x轴下方）。
2.还有就是，输入的边间值，当目标为零时；当球落在目标内和边上时的处理。
3.还有在求角度<s,v>时，如果使用公式cosA = (a.b)/(|a|.|b|), (|a|^2).(|b|^2)有可能
  超过int的范围。当然可以不计算这个值，先开方。

• Re:解题思路 (1) daofeng 2014-09-09 18:10:43