How to Check If Four Points can Make a Valid Square (C++ and Jav

  • 时间:2020-09-28 16:28:51
  • 分类:网络文摘
  • 阅读:103 次
four-points-square How to Check If Four Points can Make a Valid Square (C++ and Java)? algorithms c / c++ geometry java math programming languages

four-points-square

Given the coordinates of four points in 2D space, return whether the four points could construct a square. The coordinate (x,y) of a point is represented by an integer array with two integers.

Example:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

Note:

  • All the input integers are in the range [-10000, 10000].
  • A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  • Input points have no order.

Given four points, we may brute force all four permutation with has O(1) complexity i.e. needs to check 4!=24 cases that if any of those make a square. However, the most elegant and straightforward solution is to compute the distances between each pair, and push the distances to a set. At the end, we just have to check if there are two different lengths and also need to exclude the zeros – which may indicate that at least two points are the same (duplicate).

For example, in the following Java, we create a hash set, and store all possible distances between pairs of points. The complexity is O(1) in terms of space and time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Set<Integer> d = new HashSet();
        d.add(dist(p1, p2));
        d.add(dist(p1, p3));
        d.add(dist(p1, p4));
        d.add(dist(p2, p3));
        d.add(dist(p2, p4));
        d.add(dist(p3, p4));
        return d.size() == 2 && (!d.contains(0));
    }
    
    private int dist(int[] p1, int[] p2) {
        return (int)Math.pow(p1[0] - p2[0], 2) + (int)Math.pow(p1[1] - p2[1], 2);
    }
}
class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Set<Integer> d = new HashSet();
        d.add(dist(p1, p2));
        d.add(dist(p1, p3));
        d.add(dist(p1, p4));
        d.add(dist(p2, p3));
        d.add(dist(p2, p4));
        d.add(dist(p3, p4));
        return d.size() == 2 && (!d.contains(0));
    }
    
    private int dist(int[] p1, int[] p2) {
        return (int)Math.pow(p1[0] - p2[0], 2) + (int)Math.pow(p1[1] - p2[1], 2);
    }
}

The equivalent C++ implementation is below where we use unordered_set to store the unique distance values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int dist(vector<int> &p1, vector<int> &p2) {
        return pow(p1[0] - p2[0], 2) + pow(p1[1] - p2[1], 2);
    }
       
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        unordered_set<int> d;
        d.insert(dist(p1, p2));
        d.insert(dist(p1, p3));
        d.insert(dist(p1, p4));
        d.insert(dist(p2, p3));
        d.insert(dist(p2, p4));
        d.insert(dist(p3, p4));
        return d.size() == 2 && d.count(0) == 0;
    }
};
class Solution {
public:
    int dist(vector<int> &p1, vector<int> &p2) {
        return pow(p1[0] - p2[0], 2) + pow(p1[1] - p2[1], 2);
    }
       
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        unordered_set<int> d;
        d.insert(dist(p1, p2));
        d.insert(dist(p1, p3));
        d.insert(dist(p1, p4));
        d.insert(dist(p2, p3));
        d.insert(dist(p2, p4));
        d.insert(dist(p3, p4));
        return d.size() == 2 && d.count(0) == 0;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
不一样的雨作文  生活需要苦难作文550字  热闹的除夕作文  心如止水,乱则不明  校园的竹林作文  视频内容如何提高搜索引擎优化排名  Google SEO优化,4个“另类”的排名方法  商城系统建设心得,轻松搞定选择困难  什么是PPC?为什么你会用到它?  SEO网站优化能为你带来那些好处? 
评论列表
添加评论