You are given coordinates of four points i.e.
(x1, y1),(x2, y2),(x3, y3)and(x4, y4).Write a script to find out if the given four points form a square.
Input: x1 = 10, y1 = 20
x2 = 20, y2 = 20
x3 = 20, y3 = 10
x4 = 10, y4 = 10
Output: 1 as the given coordinates form a square.
Input: x1 = 12, y1 = 24
x2 = 16, y2 = 10
x3 = 20, y3 = 12
x4 = 18, y4 = 16
Output: 0 as the given coordinates doesn't form a square.
Squares are quadrilaterals which special properties. The defining property we will be using is that a square is a rhombus with diagonals of even length. A rhombus is a quadrilateral where all sides are of equal length.
So, we have to compare the distances of various pairs of points. The distance between two points \((x_k, y_k)\) and \((x_l, y_l)\) is given by the formula \[ \sqrt{(x_k - x_l)^2 + (y_k - y_l)^2} \]
So, if we want to compare if the distance between points \((x_k, y_k)\) and \((x_l, y_l)\) is equal to the distance between points \((x_m, y_m)\) and \((x_n, y_n)\), we need to check that
\[ \sqrt{(x_k - x_l)^2 + (y_k - y_l)^2} = \sqrt{(x_m - x_n)^2 + (y_m - y_n)^2} \]
But we can simplify this. We don't need the actual distance, all we need to know is whether two distances are equal. And if \(d_1 = d_2\), then \(d_1^2 = d_2^2\). So it suffices to check
\[ (x_k - x_l)^2 + (y_k - y_l)^2 = (x_m - x_n)^2 + (y_m - y_n)^2 \]
For most of our solutions, we will define a method dist, which gets
the coordinates of two points, and which returns the square of the
distance between the points.
We then check whether the distance between points 1 and 2, between points 2 and 3, between points 3 and 4, and between points 4 and 1, are all equal, and that the distances between points 1 and 3, and between points 2 and 4 (the diagonals) are equal.
Below, when the talk about the distance between two points, or the length of an edge or diagonal, we actually mean the square of that distance/length.
The subroutine dist:
sub dist ($x1, $y1, $x2, $y2) {($x1 - $x2) ** 2 + ($y1 - $y2) ** 2}
Then the check becomes easy. $_ contains the input:
my ($x1, $y1, $x2, $y2, $x3, $y3, $x4, $y4) = split;
say dist ($x1, $y1, $x2, $y2) == dist ($x2, $y2, $x3, $y3) ==
dist ($x3, $y3, $x4, $y4) == dist ($x4, $y4, $x1, $x2) &&
dist ($x1, $y1, $x3, $y3) == dist ($x2, $y2, $x4, $y4) ? 1 : 0
Note that in modern versions of Perl, we can chain comparisons.
That means, expr1 == expr2 == expr3 == expr4 is equivalent to
expr1 == expr2 && expr2 == expr3 && expr3 == expr4 && expr4 == expr1.
Find the full program on GitHub.
We have solutions in AWK, Bash, Bc, C, Go, Java, Lua, Node.js, Pascal, Python, Ruby, Scheme and Tcl, which are all very similar to the Perl solutions.
There are slight variations. Some languages don't have an exponentiation
operator, in which case we just multiply factors by themselves. For
instance, the dist function in Go looks like:
func dist (x1 int, y1 int, x2 int, y2 int) int {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
And in most languages, comparisons cannot be chained, so we have to split them into multiple comparisons. For instance, the test in Tcl looks like:
if {[dist $x1 $y1 $x2 $y2] == [dist $x2 $y2 $x3 $y3] &&
[dist $x2 $y2 $x3 $y3] == [dist $x3 $y3 $x4 $y4] &&
[dist $x3 $y3 $x4 $y4] == [dist $x4 $y4 $x1 $y1] &&
[dist $x1 $y1 $x3 $y3] == [dist $x2 $y2 $x4 $y4]} {
puts 1
} else {
puts 0
}
Our solution in R is slightly different. With the input in line,
we first split the input on spaces, giving us an vector with the
coordinates (as strings):
parts <- strsplit (line, " ")
Next, we create two vectors, x, and y, holding the x and y coordinates
for the four points:
x <- as.numeric (parts [[1]] [c (1, 3, 5, 7)])
y <- as.numeric (parts [[1]] [c (2, 4, 6, 8)])
The c function creates an vector with the given elements, and we use
this vector to slice out the relevant numbers. as.numeric maps strings
to numbers.
Now we create two lists with indices:
i1 <- c (1, 2, 3, 4, 1, 3)
i2 <- c (2, 3, 4, 1, 2, 4)
These correspond to the points we want the distance between (between the first and second vertex of the square, the second and third vertex of the square, etc — the last two sets are the diagonals).
Now we calculate all the distances in one operation:
z <- (x [i1] - x [i2]) ^ 2 + (y [i1] - y [i2]) ^ 2
This works, because in R, operations are done on vectors, and
basic arithmetic operations are done on each element. Now z [1] to
z [4] contain the lengths of the edges of the square, and z [5]
and z [6] contain the lengths of the diagonals.
We can now do the comparisons:
if (z [1] == z [2] && z [2] == z [3] && z [3] == z [4] && z [5] == z [6]) {
cat ("1\n")
}
else {
cat ("0\n")
}
Find the full program on GitHub.