题目地址：

https://leetcode.com/problems/valid-square/

给定平面直角坐标系里的 4 4 4个点，问它们是否能构成一个正方形。

我们可以算一下所有点对的距离，显然有个必要条件是，这些距离一共只有两个值（分别是正方形边长或者对角线长），并且长者是短者的 2 \sqrt 2 2 ​倍，且短者的点对数是长者点对数的两倍（ 4 4 4是 2 2 2的两倍）。我们考虑这是否是充分条件。容易知道满足这两个条件的两个数都是正数。不妨设四个点分别是 A , B , C , D A,B,C,D A,B,C,D。我们考虑 2 \sqrt 2 2 ​的 2 2 2个点对怎么分配。如果 A B = A C = 2 AB=AC=\sqrt 2 AB=AC=2 ​，其余点对距离都是 1 1 1，这是办不到的（因为 B D + D C ≥ B C , 1 + 1 ≥ 1 BD+DC\ge BC,1+1\ge 1 BD+DC≥BC,1+1≥1，矛盾）；那么只能是 A B = C D = 2 AB=CD=\sqrt 2 AB=CD=2 ​了，其余点对距离都是 1 1 1，这其实很容易看出了，因为 A B = 2 , A C = A D = 1 , C D = 2 AB=\sqrt 2,AC=AD=1,CD=\sqrt 2 AB=2 ​,AC=AD=1,CD=2 ​，由勾股定理， ∠ C A D \angle CAD ∠CAD是直角，剩余证明显然。代码如下：

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int[][] ps = {p1, p2, p3, p4};
        Map<Integer, Integer> map = new HashMap<>();
        int mind = Integer.MAX_VALUE, maxd = 0;
        for (int i = 0; i < ps.length; i++) {
            for (int j = i + 1; j < ps.length; j++) {
                int d = dis(ps[i], ps[j]);
                mind = Math.min(mind, d);
                maxd = Math.max(maxd, d);
                map.put(d, map.getOrDefault(d, 0) + 1);
            }
        }
        
        return map.size() == 2 && maxd == 2 * mind && map.get(maxd) * 2 == map.get(mind);
    }
    
    private int dis(int[] p1, int[] p2) {
        int d1 = p1[0] - p2[0], d2 = p1[1] - p2[1];
        return d1 * d1 + d2 * d2;
    }
}

时空复杂度 O ( 1 ) O(1) O(1)。