Consider the square with side-length
S placed in any orientation and location on the plane. The pairwise distances between points (in sorted order) are:
S, S, S, S, S*sqrt(2), S*sqrt(2). With some thinking, we can prove this is a necessary and sufficient condition [details after]. Therefore, we should only check this condition, plus that
S > 0. For convenience, we'll work with the squares of distances instead.
def validSquare(self, p1, p2, p3, p4): def dist(P, Q): return (P - Q)**2 + (P + Q)**2 D = [dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)] D.sort() return 0 < D == D == D == D and 2*D == D == D
Let's now prove our condition was necessary and sufficient.
ABCD have pairwise distances in sorted order
S, S, S, S, S*sqrt(2), S*sqrt(2). We want to show
ABCD is a square. Let us call
S a "small side" and
S*sqrt(2) a "large side". Without loss of generality, suppose
AC is a large side. If
BD is a large side, then
BC are small sides, so
B lies on the intersection of circles between
D lies on the same intersection, and thus
ABCD is a square (as two different circles of the same radius only intersect in two different points).
All other cases (
CD having a large side) are similar, so we'll only consider
AB having a large side. Then,
BC is the base of icoceles triangles
D must lie on the perpendicular bisector to
D must be closer to
A is (otherwise
|DB| > |DA| is a contradiction). Since
BDC is an equilateral triangle, angle
∠BDC = 60°, and therefore equal angles
∠ADB + ∠ADC = 300° and
∠ADB = 150°. But the sidelengths of triangle
ADB are known, which uniquely determines
∠ADB = 90°, a contradiction.