专栏名称: 九章算法

专业的北美IT求职经验分享、技术交流社区，帮助你找到好的IT工作。由硅谷顶尖IT企业工程师维护。提供专业的算法培训/面试咨询，官网 www.jiuzhang.com

Facebook面试题 | 有效正方形

九章算法 · 公众号 · 算法 · 2017-11-01 07:42

正文

作者 | 吕助教

编辑 | Cecily

专栏 | 九章算法

题目描述

给定二维平面内的四个点，判断这四个点是否能组成正方形。坐标(x,y)为整数。

输入的整数范围为 [-10000, 10000]。

样例

输入:

p1=[0,0],p2=[1,1],p3=[1,0],p4=[0,1]

输出:

Ture

说明:

[0,0],[1,1],[0,1],[1,0]四个点能够组成正方形。

解题思路分析

题目要求我们判断四个点能否组成正方形，那么正方形有哪些特征呢。我们容易想到，正方形四条边长度都相等，并且两条对角线长度也相等，所以，我们只要求出这四个点两两之间的距离，进行从小到大排序之后，如果这四个点能构成正方形，那么前面四个数就是四条边长的长度，后面两个数为两条对角线的长度，因此 我们只需要判断前四个数以及后两个数它们是否相等即可 。

这题为避免四个点重叠，因此我们还需要判断一下对角线长度是否大于边长即可。

参考程序

http://www.jiuzhang.com/solution/valid-square/