C++ 3 lines (unordered_set)


  • 18
    V

    If we calculate all distances between 4 points, 4 smaller distances should be equal (sides), and 2 larger distances should be equal too (diagonals). As an optimization, we can compare squares of the distances, so we do not have to deal with the square root and precision loss.

    Therefore, our set will only contain 2 unique distances in case of square (beware of the zero distance though).

    int d(vector<int>& p1, vector<int>& p2) {
        return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
    }
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        unordered_set<int> s({ d(p1, p2), d(p1, p3), d(p1, p4), d(p2, p3), d(p2, p4), d(p3, p4) });
        return !s.count(0) && s.size() == 2;
    }
    

  • 11
    D

    It's a wrong answer.Suppose the four points are (0,0),(0,2),(-1,√3),(1,√3),your code will return true


  • 1
    I

    but all inputs are integers


  • 3
    V

    @duwenqin123 Your test case is based on equilateral triangle. It is not possible to construct an equilateral triangle with vertices on lattice points (integers), see https://math.stackexchange.com/questions/105330/equilateral-triangle-whose-vertices-are-lattice-points.

    Therefore, this solution will work as the problem is limited to integer coordinates.

    If the problem allows decimal coordinates, then additional check will be required: 4 equal distances should be smaller than 2 equal distances.

    Though can't agree that the answer is wrong, I like the observation and test case, so I think it would be fair if I up-vote your post :)


  • 1
    A

    how about this improvement:

    class Solution {
    public:
        int d(vector<int> &p1, vector<int> &p2) {
            return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
        }
    
        bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
            unordered_set<int> s({d(p1, p2), d(p1, p3), d(p1, p4), d(p2, p3), d(p2, p4), d(p3, p4)});
            return !s.count(0) && s.size() == 2;
        }
    };
    

  • 1
    V

    @Aeonaxx nice catch; updated the solution. I initially used set, so the first position was always the smallest. Not true anymore with unordered_set. Looks like a test case is missing and that's why the unmodified solution was accepted...


  • 0
    K

    @votrubac It`s so nice that you know using the unordered_set to improve the efficiency.


  • 1
    Z

    Good solution! Here is my C++ code without hash.
    There are 3 cases in total. And all 6 distances between every two points are required for each case.

    class Solution {
    public:
        bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
            long d12 = dis(p1,p2), d13 = dis(p1,p3), d14 = dis(p1,p4), d23 = dis(p2,p3), d24 = dis(p2,p4), d34 = dis(p3,p4);
            if (d12 == d13) return d12 && d14 == d23 && d24 == d34 && d12 == d24;
            if (d12 == d14) return d12 && d13 == d24 && d23 == d34 && d12 == d23;
            if (d13 == d14) return d13 && d12 == d34 && d23 == d24 && d13 == d23;
            return false;
        }
    private:
        long dis(vector<int>& a, vector<int>& b) {
             return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);    
        }
    };
    

  • 0
    L

    Is it necessary to consider about Overflow?


  • 0
    B

    @votrubac
    a liitle change based on your idea

    class Solution {
    public:
        bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
            vector<int> s={d(p1,p2),d(p1,p3),d(p1,p4),d(p2,p3),d(p2,p4),d(p3,p4)};
            sort(s.begin(),s.end());
            if(s[0]==0||s[0]!=s[3]||s[3]>=s[4]||s[4]!=s[5]) return false;
            return true;
        }
    private:
        inline int d(vector<int>& p1,vector<int>& p2){
            return (p1[0]-p2[0])*(p1[0]-p2[0])+(p1[1]-p2[1])*(p1[1]-p2[1]);
        }
    };
    

  • 2
    H

    @votrubac said in C++ 3 lines (unordered_set):

    additional check will be required: 4 equal distances should be smaller than 2 equal distances.

    Correct me if I'm wrong: the additional you mentioned - "4 equal distances should be smaller than 2 equal distances" is still not enough. See the below example.
    0_1498564260456_Screen Shot 2017-06-27 at 7.50.21 PM.png


  • 1
    V

    @hellohowlow Your example is also based on equilateral triangle (which you cannot have in integer coordinates). There are 4 larger sides, and 2 smaller sides. Therefore, it does not pass the additional check "4 equal distances should be smaller than 2 equal distances".

    0_1498850443176_example.png


  • 0
    H

    @votrubac But in your earlier post, you said, "If the problem allows decimal coordinates, then additional check will be required..". :-P


  • 0

    @votrubac said in C++ 3 lines (unordered_set):

    If the problem allows decimal coordinates, then additional check will be required: 4 equal distances should be smaller than 2 equal distances.

    @dreamchase proved even that to be wrong as my answer had same logic - https://discuss.leetcode.com/topic/89995/simple-java-solution-square-distances/6


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.