<p>Given the coordinates of four points in 2D space <code>p1</code>, <code>p2</code>, <code>p3</code> and <code>p4</code>, return <code>true</code> <em>if the four points construct a square</em>.</p>

<p>The coordinate of a point <code>p<sub>i</sub></code> is represented as <code>[x<sub>i</sub>, y<sub>i</sub>]</code>. The input is <strong>not</strong> given in any order.</p>

<p>A <strong>valid square</strong> has four equal sides with positive length and four equal angles (90-degree angles).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
<strong>Output:</strong> false
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
<strong>Output:</strong> true
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>p1.length == p2.length == p3.length == p4.length == 2</code></li>
	<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        //analysis of solution 1:
        //solution 1 is wriong, there exists a special case:
        //                p1
        //                |
        //                |
        //                |
        //                p2
        //               /  \
        //              /    \
        //             /      \
        //            p3       p4
        //
        //dis(p1,p3) == dis(p1,p4)
        //and dis(p1,p2) == dis(p2,p3) == dis(p2,p4) == dis(p3,p4)
        //obviously, these four points can not form a valid square
        //


        /*
        //solution 1
        //both TC and SC is O(1)
        //
        auto dis = [](vector<int> &s, vector<int> &e){
            return (s[0] - e[0]) * (s[0] - e[0]) + (s[1] - e[1]) * (s[1] - e[1]);
        };

        unordered_set<int> uset{dis(p1,p2), dis(p1,p3), dis(p1,p4),
                                dis(p2,p3), dis(p2,p4), dis(p3,p4)};
        
        return uset.count(0) == 0 && uset.size() == 2;
        //end of solution 1
        */


        //analysis of solution 2:
        //move the center of the square to original potint (0,0)
        //rotate the square 90 degree(clockwise or anti-clockwise), based on the center (0,0)
        //after rotate the square 90 degree, the four points are still in the points set
        //let's say anti-clockwise 90 degree, then (x, y) becomes (-y, x)
        //


        /*
        //solution 2
        //both TC and SC is O(1)
        //
        #define c2r(p) {p[0]*4-centX, p[1]*4-centY}

        int centX = p1[0] + p2[0] + p3[0] + p4[0];
        int centY = p1[1] + p2[1] + p3[1] + p4[1];
        
        vector<array<int, 2>> pts = {c2r(p1), c2r(p2), c2r(p3), c2r(p4)};

        auto arrHash = [fn = hash<long>{}] (const array<int, 2>& arr) -> size_t {
            return fn(*((long const*)arr.data()));
        };

        unordered_set<array<int, 2>, decltype(arrHash)> uset(begin(pts),end(pts),0,arrHash);

        if(uset.size() < 4) return false;

        for(auto &pt: pts){  
            if(!uset.count({-pt[1], pt[0]})) return false;
        }

        return true;
        //end of solution 2
        */


        //solution 3, check four isosceles right triangle
        //both TC and SC is O(1)
        //
        auto dis = [](vector<int> &s, vector<int> &e){
            return (s[0] - e[0]) * (s[0] - e[0]) + (s[1] - e[1]) * (s[1] - e[1]);
        };

        auto check = [&dis](vector<int> &a, vector<int> &b, vector<int> &c){
            int d1 = dis(a,b), d2 = dis(a,c), d3 = dis(b,c);

            if(!d1 || !d2 || !d3) return false;

            return (d1 == d2 && d1 + d2 == d3) 
                || (d1 == d3 && d1 + d3 == d2)
                || (d2 == d3 && d2 + d3 == d1);
        };

        return check(p1,p2,p3) && check(p1,p2,p4) && check(p1,p3,p4) && check(p2,p3,p4);
        //end of solution 3
    }
};
29200