Geometric Algorithms II

Not a super complicated one: given four points determine whether they make a square. Notice that the square can be in any orientation, not only parallel to the axis.

The way that I solved this one was using the following algorithm:

1/ Calculate the square of the distances amongst the 4 points. There are 6 distances in total. Use long. Don't use square root, just square
2/ You want to make sure that you have 4 distances the same (call it A), and 2 distances the same (call it B)
3/ You also want to make sure that the B = 2*A as per Pythagoras 

If those conditions are met, you've got a square. Otherwise, no square. Code is down below, cheers, ACC.

Valid Square - LeetCode

593. Valid Square

Medium

Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square.

The coordinate of a point pi is represented as [xi, yi]. The input is not given in any order.

A valid square has four equal sides with positive length and four equal angles (90-degree angles).

 

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

Accepted

98,826

Submissions

225,124

public bool ValidSquare(int[] p1, int[] p2, int[] p3, int[] p4)
{
    SortedDictionary distances = new SortedDictionary();

    int[] x = { p1[0], p2[0], p3[0], p4[0] };
    int[] y = { p1[1], p2[1], p3[1], p4[1] };

    for (int i = 0; i < x.Length; i++)
    {
        for (int j = i + 1; j < x.Length; j++)
        {
            long d = PointsDistanceSquare(new int[] { x[i], y[i] }, new int[] { x[j], y[j] });
            if (!distances.ContainsKey(d)) distances.Add(d, 0);
            distances[d] = (int)distances[d] + 1;
        }
    }

    if (distances.Count != 2) return false;
    if (distances.ElementAt(0).Value != 4 || distances.ElementAt(1).Value != 2) return false;
    if (distances.ElementAt(1).Key != 2 * distances.ElementAt(0).Key) return false;

    return true;
}

private long PointsDistanceSquare(int[] p1, int[] p2)
{
    return ((long)(p1[0] - p2[0]) * (long)(p1[0] - p2[0])) + ((long)(p1[1] - p2[1]) * (long)(p1[1] - p2[1]));
}