题目

Given the coordinates of four points in 2D space, return whether the four points could construct a square.

The coordinate (x,y) of a point is represented by an integer array with two integers.

Example:

  1. Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
  2. Output: True

Note:

  1. All the input integers are in the range [-10000, 10000].
  2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  3. Input points have no order.

题意

给定四个点的坐标，判断这四个点能否组成正方形。

思路

按照x坐标从小到大、y坐标从小到大的优先级进行排序，记此时四个点为a、b、c、d，如果能形成正方形，那么四条边分别是ab、ac、bd、cd。只要判断四条边是否相等，以及对角线是否相等即可(需要先排除所有点在一个位置这一特殊情况)。

代码实现

Java

  1. class Solution {
  2.     public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
  3.         int[][] points = { p1, p2, p3, p4 };
  4.         Arrays.sort(points, (p, q) -> p[0] == q[0] ? p[1] - q[1] : p[0] - q[0]);
  5.         return calc(points[0], points[1]) != 0
  6.                 && calc(points[0], points[1]) == calc(points[0], points[2])
  7.                 && calc(points[3], points[1]) == calc(points[3], points[2])
  8.                 && calc(points[0], points[1]) == calc(points[3], points[1])
  9.                 && calc(points[0], points[3]) == calc(points[1], points[2]);
  10.     }
  12.     private int calc(int[] p, int[] q) {
  13.         int a = p[0] - q[0], b = p[1] - q[1];
  14.         return a * a + b * b;
  15.     }
  16. }