九章演算法 | Facebook面試題：有效正方形

來自專欄九章演算法 - LintCode領扣 題解5 人贊了文章

作者 | 呂助教

編輯 | 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]四個點能夠組成正方形。

解題思路分析

題目要求我們判斷四個點能否組成正方形，那麼正方形有哪些特徵呢。我們容易想到，正方形四條邊長度都相等，並且兩條對角線長度也相等，所以，我們只要求出這四個點兩兩之間的距離，進行從小到大排序之後，如果這四個點能構成正方形，那麼前面四個數就是四條邊長的長度，後面兩個數為兩條對角線的長度，因此我們只需要判斷前四個數以及後兩個數它們是否相等即可。

這題為避免四個點重疊，因此我們還需要判斷一下對角線長度是否大於邊長即可。

參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度分析

本題較為簡單，解法多樣，只要能根據正方形特徵判斷出是否為正方形，即可獲得hire評價

lintcode相關問題

最多有多少個點在一條直線上

推薦閱讀：