aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--valid_square.c46
-rw-r--r--valid_square.py41
2 files changed, 87 insertions, 0 deletions
diff --git a/valid_square.c b/valid_square.c
new file mode 100644
index 0000000..8d1bd06
--- /dev/null
+++ b/valid_square.c
@@ -0,0 +1,46 @@
+// 593. Valid Square
+#include "leetcode.h"
+
+/*
+ * given the coordinates of four points in a 2d space 'p1 .. p4', return true if
+ * the four points oncstruct 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)
+ */
+
+int dist(int x, int y) { return x * x + y * y; }
+
+bool validSquare(int *p1, int p1Size, int *p2, int p2Size, int *p3, int p3Size,
+ int *p4, int p4Size) {
+ int *p[4] = {p1, p2, p3, p4}, e[2] = {0};
+ for (int i = 0; i < 4; i++) {
+ for (int j = i + 1; j < 4; j++) {
+ int n = dist(p[i][0] - p[j][0], p[i][1] - p[j][1]);
+ if (!n)
+ return false;
+ if (n == e[0] || (!e[0] && n != e[1]))
+ e[0] = n;
+ else if (n == e[1] || (!e[1] && n != e[0]))
+ e[1] = n;
+ else
+ return false;
+ }
+ }
+ return true;
+}
+
+int main() {
+ int p11[] = {0, 0}, p21[] = {1, 1}, p31[] = {1, 0}, p41[] = {0, 1};
+ int p12[] = {0, 0}, p22[] = {1, 1}, p32[] = {1, 0}, p42[] = {0, 12};
+ int p13[] = {1, 0}, p23[] = {-1, 0}, p33[] = {0, 1}, p43[] = {0, -1};
+ printf("%d\n",
+ validSquare(p11, ARRAY_SIZE(p11), p21, ARRAY_SIZE(p21), p31,
+ ARRAY_SIZE(p31), p41, ARRAY_SIZE(p41))); // expect: 1
+ printf("%d\n",
+ validSquare(p12, ARRAY_SIZE(p12), p22, ARRAY_SIZE(p22), p32,
+ ARRAY_SIZE(p32), p42, ARRAY_SIZE(p42))); // expect: 0
+ printf("%d\n",
+ validSquare(p13, ARRAY_SIZE(p13), p23, ARRAY_SIZE(p23), p33,
+ ARRAY_SIZE(p33), p43, ARRAY_SIZE(p43))); // expect: 1
+}
diff --git a/valid_square.py b/valid_square.py
new file mode 100644
index 0000000..a9a75c1
--- /dev/null
+++ b/valid_square.py
@@ -0,0 +1,41 @@
+# 593. Valid Square
+
+"""
+given the coordinates of four points in a 2d space 'p1 .. p4', return true if
+the four points oncstruct 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)
+"""
+
+
+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
+ """
+
+ def dist(p, q):
+ return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
+
+ def check(p1, p2, p3, p4):
+ if p1[0] + p2[0] != p3[0] + p4[0] or p1[1] + p2[1] != p3[1] + p4[1]:
+ return False
+ if dist(p1, p2) != dist(p3, p4) or dist(p1, p4) != dist(p2, p4):
+ return False
+ if p1 == p2:
+ return False
+ return True
+
+ return check(p1, p2, p3, p4) or check(p1, p3, p2, p4) or check(p1, p4, p2, p3)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.validSquare(p1=[0, 0], p2=[1, 1], p3=[1, 0], p4=[0, 1]))
+ print(obj.validSquare(p1=[0, 0], p2=[1, 1], p3=[1, 0], p4=[0, 12]))
+ print(obj.validSquare(p1=[1, 0], p2=[-1, 0], p3=[0, 1], p4=[0, -1]))