Vultr DocsLatest Content

Valid Square

Updated on 07 July, 2025
Valid Square header image

Problem Statement

In the given problem, you are required to determine whether four provided points in a 2D space form a square. The points, denoted as p1, p2, p3, and p4, are structured as coordinate pairs [xi, yi]. Each point is not necessarily given in any specific order relative to its position in the square. To qualify as a square, the set of points must satisfy two main conditions:

  • All four sides formed between the points must be of equal length.
  • All angles between adjacent sides must be exactly 90 degrees.

This essentially means that not only do the lengths of the sides matter, but also the angle they make with each other, ensuring they create perpendicular bisectors at each corner point, thereby defining a perfect square.

Examples

Example 1

Input:

p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

Output:

true

Example 2

Input:

p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]

Output:

false

Example 3

Input:

p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]

Output:

true

Constraints

  • p1.length == p2.length == p3.length == p4.length == 2
  • -104 <= xi, yi <= 104

Approach and Intuition

Given the nature of a square, our approach centers on verifying two main criteria: equal side lengths and right angles. Here’s an intuitive breakdown:

Step 1: Compute Distances

Firstly, compute the squared distances between all pairs of the provided points. Squared distances are preferable over direct distance calculations to avoid the unnecessary complexity of computing square roots. For points p1 = [x1, y1] and p2 = [x2, y2], the squared distance is (x2 - x1)^2 + (y2 - y1)^2.

Step 2: Group and Verify Distances

Input four points can form six distinct distances. For these points to form a square:

  • Four of these distances should be equal (denoting the sides of the square).
  • The remaining two should also be equal (these represent the diagonals of the square, which in a square are longer and equal due to the properties of a rectangle).

Step 3: Check for Zero Length Sides

It's vital to ensure no side length is zero (as distances should be positive), which means no two points can coincide.

Step 4: Validate Right Angles

To ensure the square's integrity concerning angles, verify that where two sides of equal length intersect, they do so at a right angle. This can be confirmed using the dot product. Given three points forming two vectors, the dot product should result in zero, indicating a 90-degree angle.

By traversing through these steps, you can robustly confirm if four given points form a square in a 2D plane. The constraints that the maximum and minimum values of the coordinates are -10^4 to 10^4 and that each point is defined by two coordinates ensure that the operations are computationally feasible without concerns for overflow or floating-point inaccuracies.

Solutions

  • C++
cpp 
class Solution {
public:
    double calculateDistance(vector<int>& point1, vector<int>& point2) {
        return (point2[1] - point1[1]) * (point2[1] - point1[1]) +
               (point2[0] - point1[0]) * (point2[0] - point1[0]);
    }
    
    bool verify(vector<int>& pt1, vector<int>& pt2, vector<int>& pt3, vector<int>& pt4) {
        return calculateDistance(pt1, pt2) > 0 && calculateDistance(pt1, pt3) > 0 &&
               calculateDistance(pt1, pt2) == calculateDistance(pt2, pt3) && 
               calculateDistance(pt2, pt3) == calculateDistance(pt3, pt4) &&
               calculateDistance(pt3, pt4) == calculateDistance(pt4, pt1) && 
               calculateDistance(pt1, pt3) == calculateDistance(pt2, pt4);
    }
    
    bool isSquare(vector<int>& pt1, vector<int>& pt2, vector<int>& pt3, vector<int>& pt4) {
        return verify(pt1, pt2, pt3, pt4) || verify(pt1, pt3, pt2, pt4) ||
               verify(pt1, pt2, pt4, pt3);
    }
};

The given C++ solution involves determining whether four given points can form a square. This is performed by implementing a class, Solution, with various supporting methods.

  • calculateDistance - This method calculates the squared distance between two points, sidestepping the need for square root calculations to simplify comparison of distances.

  • verify - This secondary method checks if a given configuration of points can form a square. It ensures all sides are of equal length and that the diagonals, which connect non-adjacent points, are equal as well. The function also ensures that none of the sides have a zero length to handle the case of overlapping points.

  • isSquare - This is the main method determined to check if any permutation of the points results in a valid square by calling the verify method with different orders of points.

To determine if the four points create a square:

  1. Calculate distances between each point (essentially calculating the length of potential sides and diagonals of a square).
  2. Verify equal lengths of sides and diagonals using the verify method.
  3. Use the isSquare method to test different permutations of points arrangement to cover all possibilities that can form a square despite the sequence of input.

This logical approach ensures robust validation, considering both the properties of sides and diagonals of a square.

  • Java
java 
public class Solution {
    
    public double calculateDistance(int[] point1, int[] point2) {
        return (
            Math.pow((point2[1] - point1[1]), 2) +
            Math.pow((point2[0] - point1[0]), 2)
        );
    }
    
    public boolean verify(int[] point1, int[] point2, int[] point3, int[] point4) {
        return (
            calculateDistance(point1, point2) > 0 &&
            calculateDistance(point1, point3) > 0 &&
            calculateDistance(point1, point2) == calculateDistance(point2, point3) &&
            calculateDistance(point2, point3) == calculateDistance(point3, point4) &&
            calculateDistance(point3, point4) == calculateDistance(point4, point1) &&
            calculateDistance(point1, point3) == calculateDistance(point2, point4)
        );
    }
    
    public boolean isSquare(int[] point1, int[] point2, int[] point3, int[] point4) {
        return (
            verify(point1, point2, point3, point4) ||
            verify(point1, point3, point2, point4) ||
            verify(point1, point2, point4, point3)
        );
    }
}

The provided Java solution aims to determine if four given points form a square. The approach is carried out through the following methods:

  • calculateDistance(int[] point1, int[] point2): Calculates the Euclidean distance squared between two points, avoiding floating point operations by not taking the square root. This method efficiently checks distance equality.

  • verify(int[] point1, int[] point2, int[] point3, int[] point4): Checks if the distances between the given points fulfill the conditions of a square. Specifically:

    • All sides must have the same length.
    • The diagonals, connecting opposite corners, must have equal lengths as well.
    • It ensures no duplicate points exist (distance should be greater than zero).

  • isSquare(int[] point1, int[] point2, int[] point3, int[] point4): Verifies multiple combinations of point orderings:

    • Original order [point1, point2, point3, point4]
    • Swapped diagonals or sides [point1, point3, point2, point4] and [point1, point2, point4, point3]

These checks cater to different possible spatial arrangements of the points that still form the same square shape. By ensuring that all conditions to form a square are met, this method effectively confirms the configuration of a square with robustness against varied input sequences.

  • Python
python 
class Geometry:
    def calculate_distance(self, point1, point2):
        return (point2[1] - point1[1]) ** 2 + (point2[0] - point1[0]) ** 2
    
    def check_square(self, p1, p2, p3, p4):
        return (
            self.calculate_distance(p1, p2) > 0
            and self.calculate_distance(p1, p3) > 0
            and self.calculate_distance(p1, p2) == self.calculate_distance(p2, p3)
            and self.calculate_distance(p2, p3) == self.calculate_distance(p3, p4)
            and self.calculate_distance(p3, p4) == self.calculate_distance(p4, p1)
            and self.calculate_distance(p1, p3) == self.calculate_distance(p2, p4)
        )
    
    def is_valid_square(self, p1, p2, p3, p4):
        return (
            self.check_square(p1, p2, p3, p4)
            or self.check_square(p1, p3, p2, p4)
            or self.check_square(p1, p2, p4, p3)
        )

The provided Python 3 code defines a class Geometry with methods to determine if four points form a valid square. The process breaks down into calculating distances between points and checking equalities fulfilling the criteria for a square.

  • The method calculate_distance computes the square of the Euclidean distance between two points using the formula: (difference in y-coordinates)² + (difference in x-coordinates)².

  • The method check_square verifies if all sides have equal length and the diagonals are equal, essential conditions for a square:

    • It first ensures all pairs of points define a line segment with a non-zero distance.
    • It then checks equality of distances between consecutive points (sides of the potential square) and confirms that distances between opposite vertex pairs (diagonals) are equal.

  • The main method is_valid_square thoroughly tests various permutations of the input points by trying different combinations and orientations to confirm if any satisfy the criteria of being a square, which caters to multiple arrangements of the input.

The methods use conditional statements to enforce logical checks and mathematical calculations to determine if the given points form a valid square. This allows flexibility to handle varying order of points, hence offering a robust solution.

Comments

No comments yet.