Valid Square Problem


Description

LeetCode Problem 593.

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 p_i is represented as [x_i, y_i]. 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:

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

Example 2:

1
2
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output: false

Example 3:

1
2
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
  • -10^4 <= x_i, y_i <= 10^4


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    // helper function to calculate distance between two points
    double dist(vector<int>& p1, vector<int>& p2) {
        return sqrt((p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]));
    }
    
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        // keep points in an array to be able to get them by index
        vector<vector<int>> points = {p1, p2, p3, p4};
        set<double> lengths;
        
        for (int i=0; i<4; i++) {
            for (int j=i+1; j<4; j++) {
                double curr = dist(points[i], points[j]);
                if (curr != 0)
                    lengths.insert(curr);
                
                // if distance is zero - we got a duplicated point
                else
                    return false;
            }
        }
        // We are supposed to end with only two different lengths: the sides and the diagonals
        return lengths.size() == 2;
    }
};




Related Posts

Rectangle Overlap Problem

LeetCode 836. An axis-aligned rectangle is represented as a list...

Mirror Reflection Problem

LeetCode 858. There is a special square room with mirrors...

Minimum Area Rectangle II Problem

LeetCode 963. You are given an array of points in...

Largest Triangle Area Problem

LeetCode 812. Given an array of points on the X-Y...

Erect The Fence Problem

LeetCode 587. You are given an array trees where trees[i]...

Valid Square Problem

LeetCode 593. Given the coordinates of four points in 2D...