Welcome to Subscribe On Youtube
-
import java.util.ArrayList; import java.util.Arrays; /* 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. */ public class Valid_Square { // Just find the square of lengths, and validate that // 1. There are only two equal longest lengths. // 2. The non longest lengths are all equal. (or, a^2 + b^2 = c^2) public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { // long in case of int overflow long[] lengths = new long[]{ getDistLong(p1, p2), getDistLong(p2, p3), getDistLong(p3, p4), getDistLong(p4, p1), getDistLong(p1, p3), getDistLong(p2, p4) }; // all 6 sides long max = 0, nonMax = 0; for (long len : lengths) { max = Math.max(max, len); } int count = 0; for (int i = 0; i < lengths.length; i++) { if (lengths[i] == max) count++; else nonMax = lengths[i]; // non diagonal side. } if (count != 2) return false; // diagonals lenghts have to be same. for (long len : lengths) { if (len != max && len != nonMax) return false; // sides have to be same length } return true; } private long getDistLong(int[] p1, int[] p2) { return (long) Math.pow(p1[0] - p2[0], 2) + (long) Math.pow(p1[1] - p2[1], 2); } // more math other than algorithmn // 2 pairs of parellel lines, and check 1 angle is 90^ (then rest 3 also 90^), special: vertical line case // or, 4 lines are same length, and and check 1 angle is 90^ (then rest 3 also 90^) // or, 4 lines are same length, and a^2 + b^2 = c^2 // getting too many redundancy of computation of diagonal and edge public class Solution_shitty { public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { if(p1 == null || p2 == null || p3 == null || p4 == null) { return false; } // generate baseline from p1, can make 3 lines int d1 = getDist(p1, p2); int d2 = getDist(p1, p3); int d3 = getDist(p1, p4); int diagonal = Math.max(Math.max(d1, d2), d3); int edge = Math.min(Math.min(d1, d2), d3); // iterate through rest 3 points // @note: type initialization ArrayList<int[]> all3 = new ArrayList<>(Arrays.asList(p2, p3, p4)); for(int[] each: all3) { // edges are the same // diagonal is the same } return true; } // assume valid input of point private int getDist(int[] p1, int[] p2) { return (int) (Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2)); } } } ############ class Solution { public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4); } private boolean check(int[] a, int[] b, int[] c) { int x1 = a[0], y1 = a[1]; int x2 = b[0], y2 = b[1]; int x3 = c[0], y3 = c[1]; int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3); int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3); if (d1 == d2 && d1 + d2 == d3 && d1 > 0) { return true; } if (d1 == d3 && d1 + d3 == d2 && d1 > 0) { return true; } if (d2 == d3 && d2 + d3 == d1 && d2 > 0) { return true; } return false; } }
-
// OJ: https://leetcode.com/problems/valid-square/ // Time: O(1) // Space: O(1) class Solution { private: long long dist(vector<int>& a, vector<int>& b) { return pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2); } public: bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) { map<long long, int> m; vector<vector<int>> v = {p1, p2, p3, p4}; for (int i = 0; i < 3; ++i) { for (int j = i + 1; j < 4; ++j) { auto d = dist(v[i], v[j]); if (!d) return false; m[d]++; } } auto a = *m.begin(), b = *m.rbegin(); return m.size() == 2 && a.second == 4 && 2 * a.first == b.first; } };
-
class Solution: def validSquare( self, p1: List[int], p2: List[int], p3: List[int], p4: List[int] ) -> bool: def check(a, b, c): (x1, y1), (x2, y2), (x3, y3) = a, b, c d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3) d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3) return any( [ d1 == d2 and d1 + d2 == d3 and d1, d2 == d3 and d2 + d3 == d1 and d2, d1 == d3 and d1 + d3 == d2 and d1, ] ) return ( check(p1, p2, p3) and check(p2, p3, p4) and check(p1, p3, p4) and check(p1, p2, p4) ) ############ class Solution(object): def validSquare(self, p1, p2, p3, p4): """ :type p1: List[int] :type p2: List[int] :type p3: List[int] :type p4: List[int] :rtype: bool """ dist = lambda a, b: ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) sideLens = set([dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)]) if len(sideLens) != 2 or 0 in sideLens: return False return True
-
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool { check := func(a, b, c []int) bool { x1, y1 := a[0], a[1] x2, y2 := b[0], b[1] x3, y3 := c[0], c[1] d1 := (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) d2 := (x1-x3)*(x1-x3) + (y1-y3)*(y1-y3) d3 := (x2-x3)*(x2-x3) + (y2-y3)*(y2-y3) if d1 == d2 && d1+d2 == d3 && d1 > 0 { return true } if d1 == d3 && d1+d3 == d2 && d1 > 0 { return true } if d2 == d3 && d2+d3 == d1 && d2 > 0 { return true } return false } return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4) }
-
class Solution { public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { if (p1[0] == p2[0] && p1[1] == p2[1]) return false; if (p1[0] == p3[0] && p1[1] == p3[1]) return false; if (p1[0] == p4[0] && p1[1] == p4[1]) return false; if (p2[0] == p3[0] && p2[1] == p3[1]) return false; if (p2[0] == p4[0] && p2[1] == p4[1]) return false; if (p3[0] == p4[0] && p3[1] == p4[1]) return false; int[] distanceSquares = new int[6]; distanceSquares[0] = distanceSquare(p1, p2); distanceSquares[1] = distanceSquare(p1, p3); distanceSquares[2] = distanceSquare(p1, p4); distanceSquares[3] = distanceSquare(p2, p3); distanceSquares[4] = distanceSquare(p2, p4); distanceSquares[5] = distanceSquare(p3, p4); Arrays.sort(distanceSquares); if (distanceSquares[0] != distanceSquares[1] || distanceSquares[1] != distanceSquares[2] || distanceSquares[2] != distanceSquares[3]) return false; else if (distanceSquares[4] != distanceSquares[5]) return false; else return true; } public int distanceSquare(int[] p1, int[] p2) { return (p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]); } } ############ class Solution { public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4); } private boolean check(int[] a, int[] b, int[] c) { int x1 = a[0], y1 = a[1]; int x2 = b[0], y2 = b[1]; int x3 = c[0], y3 = c[1]; int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3); int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3); if (d1 == d2 && d1 + d2 == d3 && d1 > 0) { return true; } if (d1 == d3 && d1 + d3 == d2 && d1 > 0) { return true; } if (d2 == d3 && d2 + d3 == d1 && d2 > 0) { return true; } return false; } }
-
// OJ: https://leetcode.com/problems/valid-square/ // Time: O(1) // Space: O(1) class Solution { private: long long dist(vector<int>& a, vector<int>& b) { return pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2); } public: bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) { map<long long, int> m; vector<vector<int>> v = {p1, p2, p3, p4}; for (int i = 0; i < 3; ++i) { for (int j = i + 1; j < 4; ++j) { auto d = dist(v[i], v[j]); if (!d) return false; m[d]++; } } auto a = *m.begin(), b = *m.rbegin(); return m.size() == 2 && a.second == 4 && 2 * a.first == b.first; } };
-
class Solution: def validSquare( self, p1: List[int], p2: List[int], p3: List[int], p4: List[int] ) -> bool: def check(a, b, c): (x1, y1), (x2, y2), (x3, y3) = a, b, c d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3) d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3) return any( [ d1 == d2 and d1 + d2 == d3 and d1, d2 == d3 and d2 + d3 == d1 and d2, d1 == d3 and d1 + d3 == d2 and d1, ] ) return ( check(p1, p2, p3) and check(p2, p3, p4) and check(p1, p3, p4) and check(p1, p2, p4) ) ############ class Solution(object): def validSquare(self, p1, p2, p3, p4): """ :type p1: List[int] :type p2: List[int] :type p3: List[int] :type p4: List[int] :rtype: bool """ dist = lambda a, b: ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) sideLens = set([dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)]) if len(sideLens) != 2 or 0 in sideLens: return False return True
-
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool { check := func(a, b, c []int) bool { x1, y1 := a[0], a[1] x2, y2 := b[0], b[1] x3, y3 := c[0], c[1] d1 := (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) d2 := (x1-x3)*(x1-x3) + (y1-y3)*(y1-y3) d3 := (x2-x3)*(x2-x3) + (y2-y3)*(y2-y3) if d1 == d2 && d1+d2 == d3 && d1 > 0 { return true } if d1 == d3 && d1+d3 == d2 && d1 > 0 { return true } if d2 == d3 && d2+d3 == d1 && d2 > 0 { return true } return false } return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4) }