0593. Valid Square ================== 题目信息 -------- :题号: 0593 :难度: Medium :主题: 平面几何、四个点、边长、对角线 :原题: `LeetCode 0593 `_ :重点: 四点顺序任意、正方形必须有四条相等非零边和两条相等对角线、重复点不能成正方形 题目重述 -------- 给定平面上的四个整数坐标点 ``p1``、``p2``、``p3``、``p4``,判断它们能否作为某个正方形的四个顶点。 输入点的排列顺序没有几何含义。合法正方形必须具有正面积:四条边长度相等且非零,两条对角线长度相等,并且对角线长于边;若存在重复点、退化图形或仅构成长方形、菱形等其他形状,返回 ``false``。 自建示例 -------- 轴对齐正方形: .. code-block:: text 输入:p1 = [0,0],p2 = [2,0],p3 = [2,2],p4 = [0,2] 输出:true 解释:四条边长度均为 2,两条对角线长度也相等,四点构成正方形。 长方形不是正方形: .. code-block:: text 输入:p1 = [0,0],p2 = [3,0],p3 = [3,2],p4 = [0,2] 输出:false 解释:相邻边长度分别为 3 和 2,并不全部相等。 六个点对距离判定边和对角线 ---------------------------- 四个顶点的排列顺序未知,不能直接假定输入顺序对应相邻点。计算六个点对的平方距离并排序:正方形应有四个相等且非零的边长平方,另外两个相等的对角线平方,并且对角线平方恰好是边长平方的两倍。 C++ 实现 -------- .. code-block:: cpp class Solution { long long distanceSquared(const std::vector& a, const std::vector& b) { long long dx = static_cast(a[0]) - b[0]; long long dy = static_cast(a[1]) - b[1]; return dx * dx + dy * dy; } public: bool validSquare(std::vector& p1, std::vector& p2, std::vector& p3, std::vector& p4) { std::vector> points = {p1, p2, p3, p4}; std::vector distances; for (int i = 0; i < 4; ++i) { for (int j = i + 1; j < 4; ++j) { distances.push_back( distanceSquared(points[i], points[j])); } } std::sort(distances.begin(), distances.end()); return distances[0] > 0 && distances[0] == distances[3] && distances[4] == distances[5] && distances[4] == 2 * distances[0]; } }; 代码分析 -------- 重复点会产生零距离并被第一项条件排除;排序后的前四项相等保证四条边一致,后两项相等且为两倍则保证它们是同一组正方形对角线。平方距离避免浮点误差,六个点对的计算次数固定,时间和额外空间复杂度均为 ``O(1)``。