Brute Force Approach

A naive approach to solving this problem would be to calculate the distance between every pair of points. For four points to form a square, we need to verify that there are four sides of equal length and two diagonals of equal length. Also, we need to ensure that the side length is not zero, and the points are distinct.

Algorithm

1. Calculate all possible distances between the points.
2. Check if there are exactly four sides of equal length (side).
3. Check if there are exactly two diagonals of equal length (diagonal).
4. Verify that the side length is greater than zero and diagonal length is greater than zero.
5. Verify that diagonal length is equal to side length multiplied by sqrt(2).

Code

import math

def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)


def is_square_brute_force(p1, p2, p3, p4):
    distances = []
    points = [p1, p2, p3, p4]

    for i in range(4):
        for j in range(i + 1, 4):
            distances.append(distance(points[i], points[j]))

    distances.sort()

    # Check for equal sides and equal diagonals
    if distances[0] > 0 and \
       abs(distances[0] - distances[1]) < 1e-6 and \
       abs(distances[0] - distances[2]) < 1e-6 and \
       abs(distances[0] - distances[3]) < 1e-6 and \
       abs(distances[4] - distances[5]) < 1e-6 and \
       abs(distances[4] / distances[0] - math.sqrt(2)) < 1e-6:
        return True

    return False

Time Complexity

O(1) because we have a fixed number of calculations.

Space Complexity

O(1) because we use a fixed amount of extra space.

Optimal Approach

An optimized approach still calculates distances but does so more strategically. We can use a set to store the distances to ensure we don't have zero length sides or duplicate points. Then, we verify if the count of unique distances are 2. The larger distance must be sqrt(2) times of the smaller distance to form a square.

Algorithm

1. Calculate the distance between every pair of points.
2. Add the distances to a set.
3. If the size of set is not equal to 2, return false.
4. Check if the ratio of larger distance to smaller distance is approximately sqrt(2)

Code

import math

def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)


def is_square(p1, p2, p3, p4):
    distances = set()
    points = [p1, p2, p3, p4]

    for i in range(4):
        for j in range(i + 1, 4):
            dist = distance(points[i], points[j])
            if dist == 0:
                return False # handles duplicate points
            distances.add(dist)

    if len(distances) != 2:
        return False

    distances = sorted(list(distances))
    if abs(distances[1] / distances[0] - math.sqrt(2)) < 1e-6:
        return True

    return False

Time Complexity

O(1) because we have a fixed number of calculations regardless of the input size.

Space Complexity

O(1) because the set will hold a maximum of two distinct distances.

Edge Cases

• Duplicate Points: If any two points are the same, it cannot form a square.
• Zero Length: If the side length is zero, it's not a valid square.
• Floating Point Precision: Use a tolerance when comparing floating-point numbers to account for precision issues.