CheckIO - Area of a convex polygon

CheckIO - Area of a convex polygon

CHECKIO, PYTHON

http://www.checkio.org/mission/task/info/area-of-a-convex-polygon/python-27/

一句话——求给出凸多边形的面积。请注意:1. 凸多边形,别去想什么凹多边形的例子了; 2. 没有说是正N变形,那个公式在这里是用不了的。

多边形的面积,能想到的就只有三角形了——已知三角形的三条边长,可以得出三角形面积。那么我们可以考虑这样对任务进行分解:

  1. 将多边形分成N个三角形;
  2. 对N个三角形进行累加求和。
我相信第二点是很容易的,参照百科的文档谁都能写。那么我们需要想想第一点怎么实现。我们选定一点作为基点,由于是凸多边形,那么其他所有的点都在这个点180度的范围内。为了方便计算,我们就用Y值最小的一个点就行,这样所有的点都在他上方(或者水平方向有一个点,且最多只能有一个!)。然后反余弦函数可以求出以基点为中心,与X轴正方向的夹角。按照夹角大小排序,之后每次顺序取出两个点和基点就可以组成N-2个没有重复的三角形了。
代码如下:


到此我相信已经可以返回结果了,但是现在才是纯粹数学之后的编程技巧。

尝试测试一下
assert checkio([[1, 1], [9, 9], [9, 1]]) == 32, "The half of the square"
结果很意外吧,居然通不过!是的,就是通不过。那我们print出来看看,结果是32.0。呀〜原来是类型不对,现不管后面的测试,用int转换类型试试——31

你敢信!!!
int(32.0) == 31

别急,我们用as_integer_ratio这个浮点数内置方法来看看结果,结果是:
(4503599627370495, 140737488355328)
多么诡异的数值!别急,试试直接使用32.0来看看结果
In [72]: a = 32.0

In [73]: a.as_integer_ratio()
Out[73]: (32, 1)

In [74]: a = 35.5

In [75]: a.as_integer_ratio()
Out[75]: (71, 2)
原来如此,我们print看到的32.0,是上面两个数相除得到的结果。我们计算的结果,虽然看起来是32.0,但是实际却不是!那么简单了 ,既然要求到0.1,我们先用进行四舍五入到小数点后面第一位。然后as_integer_ratio函数还解决了我们另外一个问题——何时返回整数,何时返回小数。把这里补完,就是上面贴的完整代码了。

comments powered by Disqus