Preface explains

Algorithm learning, daily brush record.

Subject to connect

Valid square

The subject content

Given the coordinates of four points in a two-dimensional space, returns whether four points can form a square.

The coordinates of a point (x, y) are represented by an array of integers 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 of [-10000, 10000].

A valid square has four equal positive lengths and four equal angles (90 degree angles).

Input points are not in order.

The analysis process

Here’s how I did the analysis. I came up with method 1, but method 1 was wrong; Method 2 was later improved, but method 2 was also wrong; Then it improves to method 3, but method 3 is also wrong; Then it was improved to method 4, which was finally correct. Finally, I came up with method 5, which was solved with another more concise idea.

Method 1(error)

If four points can form a square, then three points can form a triangle, so the Pythagorean theorem is used to determine whether three points can form a triangle.

Find the distance between two points using the formula for finding the distance:

P13, p23, p12 ^ 2 + P13 ^ 2 = P14 ^ 2, p12 ^ 2 + P13 ^ 2 = P14 ^ 2.

The code is as follows:

Class Solution {public Boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {public Boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { The distance from point a and point b = (a ^ 2 + b ^ 2) the square root of a double p12 = math.h SQRT (math.h pow ((p1 [0] - p2 [0]), 2) + math.h pow ((p1 [1] - p2 [1]), 2)); / / the distance between p1 and p3 double p13 = math.h SQRT (math.h pow ((p1 p3 is [0] - [0]), 2) + math.h pow ((p1 [1] - p3 [1]), 2)); / / the distance between p1 and p4 double p14 = math.h SQRT (math.h pow ((p1 [0] - p4 [0]), 2) + math.h pow ((p1 [1] - p4 [1]), 2)); If p12^2 + p13^2 = p23^2, then the three points form a triangle. If p12^2 + p13^2 = p23^2, then the intersecting lines are equal, so p14 = p23, P12 ^2 + p13^2 = p14^2 (p12^2 + p13^2 = p14^2) The order may be different here, so there are three cases to judge, Meet) in the case of a return math.h pow (p12, 2) + math.h pow (p13, 2) = = math.h pow (p14, 2) | | math.h pow (p12, 2) + math.h pow (p14, 2) == Math.pow(p13, 2) || Math.pow(p13, 2) + Math.pow(p14, 2) == Math.pow(p12, 2); }}Copy the code

But it hasn’t been committed, and just executing the code turns out to be wrong.

Why is that? Because the square root causes a loss of accuracy, and even if three points make a triangle, it doesn’t prove that four points make a square, it could be a rectangle.

Method 2(Error)

Therefore, I improved method 1 to determine whether three points can form an isosceles right triangle.

When calculating the distance, only calculate the square of the distance, because the square of the distance and then take the square of the distance, first of all, it is superfluous, secondly, the accuracy will be lost after taking the square of the distance, leading to the error of the result.

P13 and P23 are still chosen as pp12, p13 and p23, because p23 = P14 if it is a square, so it is converted to determine whether p12 ^ 2 + p13 ^ 2 = p14 ^ 2 is valid.

The code is as follows:

Class Solution {public Boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {class Solution {public Boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { The distance of the point a and point b = (a ^ 2 + b ^ 2) the square root of a double p12 = math.h pow ((p1 [0] - p2 [0]), 2) + math.h pow ((p1 [1] - p2 [1]), 2); If (p12 == 0) {// // p1 and p2 cannot be repeated. If the square of the two points is 0, then the two points are 0. } / / p1 and p3 the square of the distance between the double p13 = math.h pow ((p1 p3 is [0] - [0]), 2) + math.h pow ((p1 p3 is [1] - [1]), 2); If (p13 == 0) {return false; } / / p1 and p4 the square of the distance between the double p14 = math.h pow ((p1 [0] - p4 [0]), 2) + math.h pow ((p1 [1] - p4 [1]), 2); If (p14 == 0) {return false; } // If p12 == p13 and p12^2 + p13^2 = p23^2, then these three points form an isosceles right triangle. If p12 == p13 + p13^2 = p23^2, then the intersecting lines are equal, so p14 = p23, P12 ^2 + p13^2 = p14^2 (p12^2 + p13^2 = p14^2) This order may be different, so to determine three conditions, meet) in the case of a / / here in front of the square root, retains the square directly, here to judge when directly using the above calculation good to judge / / not in front of the square root, because after the root of precision will be lost, after the root of square again here, Is not the original value of the return (p12 = = p13 && p12 + p13 = = p14) | | (p12 = = p14 && p12 + p14 = = p13) | | (p13 = = p14 && p13 + p14 = = p12); }}Copy the code

A runtime error message is displayed after submitting code.

The input of [0,1],[1,2],[0,2],[0,0] is incorrect.

Our analysis shows that [0,1],[1,2],[0,2],[0,0] are actually three points on a straight line, which cannot form a square, as shown in the figure:

If p1 is point A, P2 is point D, p3 is point C, p4 is point B, then P12 ^ 2 = 1, p13 ^ 2 = 1, p14 ^ 2 = 2, exactly p12 = p13, and P12 + p13 = p14.

As can be seen from the figure, another diagonal line cannot be used to judge whether a triangle can be formed. P12, P13 and P23 must be used to judge whether a triangle can be formed. P23 cannot be replaced by P14.

Method 3(Error)

According to the above conclusion, it is not possible to use another diagonal line to judge whether a triangle can be formed, but p12, P13 and P23.

The code is as follows:

Class Solution {public Boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {class Solution {public Boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { The distance of the point a and point b = (a ^ 2 + b ^ 2) the square root of a double p12 = math.h pow ((p1 [0] - p2 [0]), 2) + math.h pow ((p1 [1] - p2 [1]), 2); If (p12 == 0) {// // p1 and p2 cannot be repeated. If the square of the two points is 0, then the two points are 0. } / / p1 and p3 the square of the distance between the double p13 = math.h pow ((p1 p3 is [0] - [0]), 2) + math.h pow ((p1 p3 is [1] - [1]), 2); If (p13 == 0) {return false; } / / p2 and p3 the square of the distance between the double p23 = math.h pow ((p2 p3 is [0] - [0]), 2) + math.h pow ((p2 [1] - p3 [1]), 2); If (p23 == 0) {return false; } // If p12 == p13 and p12^2 + p13^2 = p23^2, the three points form an isosceles right triangle. This order may be different, so to determine three conditions, meet) in the case of a / / here in front of the square root, retains the square directly, here to judge when directly using the above calculation good to judge / / not in front of the square root, because after the root of precision will be lost, after the root of square again here, Is not the original value of the return (p12 = = p13 && p12 + p13 = = p23) | | (p12 = = p23 && p12 + p23 = = p13) | | (p13 = = p23 && p13 + p23 = = p12); }}Copy the code

However, after submitting the code, it still prompts you with a runtime error.

The input of [0,1],[1,1],[1,0],[0,2] is incorrect.

Our analysis shows that [0,1],[1,1],[1,0],[0,2], is actually a diamond, as shown in figure:

P12 ^ 2 = 1, p13 ^ 2 = 1, p23 ^ 2 = 2, p12 = p13, and P12 + p13 = p23.

Therefore, it is not enough to determine whether a pair of three points can form an isosceles right triangle, it is necessary to determine whether any three points can form an isosceles right triangle.

Method 4(True)

According to the previous idea, determine whether any three points can form an isosceles right triangle.

Change method 3 above to a function that specifically determines whether three points can form an isosceles right triangle.

Call this function four times, pass in four cases, if each case returns true, then each case will form an isosceles right triangle, then any three points will form an isosceles right triangle, then these four points will form a square.

The code is as follows:

class Solution { public boolean validSquare(int[] p1, int[] p2, int[] p3, Return judgeTriangle(p1, P2, p3) &&judgetriangle (p1, P2, p4) &&judgetriangle (p1, P2, p4) p3, p4) && judgeTriangle(p2, p3, p4); } private Boolean judgeTriangle(int[] p1, int[] p2, int[] p3) {private Boolean judgeTriangle(int[] p1, int[] p2, int[] p3) { The distance of the point a and point b = (a ^ 2 + b ^ 2) the square root of a double p12 = math.h pow ((p1 [0] - p2 [0]), 2) + math.h pow ((p1 [1] - p2 [1]), 2); If (p12 == 0) {// // p1 and p2 cannot be repeated. If the square of the two points is 0, then the two points are 0. } / / p1 and p3 the square of the distance between the double p13 = math.h pow ((p1 p3 is [0] - [0]), 2) + math.h pow ((p1 p3 is [1] - [1]), 2); If (p13 == 0) {return false; } / / p2 and p3 the square of the distance between the double p23 = math.h pow ((p2 p3 is [0] - [0]), 2) + math.h pow ((p2 [1] - p3 [1]), 2); If (p23 == 0) {return false; // If p12 == p13 and p12^2 + p13^2 = p23^2, then the three points form a regular triangle. If p12 == p13 + p13^2 = p23^2, then the intersecting lines are equal, so p14 = p23, P12 ^2 + p13^2 = p14^2 (p12^2 + p13^2 = p14^2) This order may be different, so to determine three conditions, meet) in the case of a / / here in front of the square root, retains the square directly, here to judge when directly using the above calculation good to judge / / not in front of the square root, because after the root of precision will be lost, after the root of square again here, Is not the original value of the return (p12 = = p13 && p12 + p13 = = p23) | | (p12 = = p23 && p12 + p23 = = p13) | | (p13 = = p23 && p13 + p23 = = p12); }}Copy the code

When the code is submitted, it is prompted to run correctly.

It took 1ms to execute, beating 80.58% of users in time, 36.4MB in memory consumption, and beating 13.27% in space.

Method 5(True)

I found the previous idea too complicated, so I decided to ditch it and switch to something else.

So let’s figure out the distance between any two points, six distances.

If these six distances have no zeros and only two kinds of distances, then it’s a square.

The code is as follows:

Class Solution {public Boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {class Solution {public Boolean validSquare(int[] p2, int[] p3, int[] p4) { // The distance between P1 and p2 squared, according to the formula, The distance of the point a and point b = (a ^ 2 + b ^ 2) the square root of a double p12 = math.h pow ((p1 [0] - p2 [0]), 2) + math.h pow ((p1 [1] - p2 [1]), 2); Double p13 = math.pow ((p1[0] -p3 [0]), 2) + math.pow ((p1[1] -p3 [1]), 2); double p13 = math.pow ((p1[0] -p3 [0]), 2); Double p14 = math.pow ((p1[0] -p4 [0]), 2) + math.pow ((p1[1] -p4 [1]), 2); double p14 = math.pow ((p1[1] -p4 [0]), 2); Double p23 = math.pow ((p2[0] -p3 [0]), 2) + math.pow ((p2[1] -p3 [1]), 2); double p23 = math.pow ((p2[0] -p3 [0]), 2); Double p24 = math.pow ((p2[0] -p4 [0]), 2) + math.pow ((p2[1] -p4 [1]), 2); double p24 = math.pow ((p2[0] -p4 [0]), 2); Double p34 = math.pow ((p3[0] -p4 [0]), 2) + math.pow ((p3[1] -p4 [1]), 2); double p34 = math.pow ((p3[0] -p4 [0]), 2); Double [] Accommodate = {p12, p13, p14, p23, p24, p34}; List<Double> list = new ArrayList<>(); // For (double distance: Accommodate) {if (distance == 0) {// If both points coincide, then they cannot form squares. } if (! Contains (distance)) {// If the list does not contain the square of the distance, add to the list list list.add(distance); Return list.size() == 2; return list.size() == 2; }}Copy the code

When the code is submitted, it is prompted to run correctly.

It took 1ms to execute, beating 89.58% of users in time, 36.1MB in memory consumption, and 74.52% in space.

Summarize the problem solving

First, the calculation of distance can not be directly applied to the formula of distance calculation, directly compare the sum of squares of coordinate difference of two points, do not take the square root, time-consuming and loss of accuracy.

Second, when determining whether three points can form a triangle, you can’t use another diagonal line instead.

Third, no two points can be repeated, no three points can be on a straight line.

Fourth, if the distance between any two points does not appear to be zero and there are only two distances, then it is a square.

The original link

Original link: valid square