【奇怪的训练】Four Points

11/17/2014

题意描述:给定平面上四个点,求它的一个外接正方形。

 

解法:

稍有常识的人即可看出,

最上、最下的两个点做平行于X轴的线,

最左、最右的两个点做平行于Y轴的线,

这是一定可以构造出一个外接矩形的。

那么稍有常识的人便可看出,

假如我们构造出了一个w>h的矩形,

那么将四个点顺时针旋转90°(立起来),

就可以得到h>w的矩形。

那么问题来了,

在这个旋转过程中是否可以形成一个w=h的矩形,即我们需要的正方形呢?

答案是显而易见的。。

因此,我们在[0,π/2]区间内二分需要旋转的弧度,

然后判断形成的矩形是否是正方形即可。

 

 

-----------------------------反正也没人看我的博客,谁想做这道题加我qq来要链接好了= =