Want to create interactive content? It’s easy in Genially!

POWER OF ALGORITHM PRESENTATION

yogita zirange

Created on November 6, 2023

Start designing with a free template

Discover more than 1500 professional designs like these:

Explore all templates

How to check if given four points forms a square

APPROACH

The approach is as follows:* Define a class Point with two fields x and y to represent the coordinates of a point. *Define a method distanceSquare that takes another Point object as a parameter and returns the square of the distance between the two points. *Define a static method checkIfSquare that takes four Point objects as parameters and returns a boolean value indicating if they form a square or not. * The logic of the checkIfSquare method is based on the fact that a square has four equal sides and two equal diagonals. Therefore, we can use a HashSet to store the six distances between the four points and check if there are only two distinct values in the set. *One of them must be the side length and the other must be the diagonal length. Moreover, the diagonal length must be twice the side length. If these conditions are satisfied, then the points form a square, otherwise not. * Define a main method that creates four Point objects with some coordinates and calls the checkIfSquare method to print the result.

+ info

In order to know the distance between 2 points we have the following formula as AB = √[(x2−x1)2 + (y2−y1)2] Where, Coordinate of A is (x1,y1) Coordinate of B is (x2,y2)

TO CHECK DISTANCE BETWEEN TO POINTS

+ info

ALGORITHM

If the size of the set is not 2, return false Convert the set to a list and sort it in ascending order. If the first element is not half of the second element, return false. Return true

The algorithm can be summarized as follows: Input: Four Point objects p1, p2, p3, p4 Output: A boolean value indicating if the points form a square or not Steps: Initialize a HashSet distance to store the distances between the points Add the distance squares between p1 and p2, p1 and p3, p1 and p4, p2 and p3, p2 and p4, and p3 and p4 to the set

+ info

TIME COMPLEXITY The time complexity of the program is O(1) because the number of operations is constant and does not depend on the input size.

SPACE COMPLEXITY

The space complexity of the program is O(1) because the HashSet uses a fixed amount of memory and does not grow with the input size.

OTHER WAY TO SOLVE THIS PROGRAM

if (d2 == d3 && 2 * d2 == d4 && 2 * distSq(p2, p4) == distSq(p2, p3)) { return true; } // The below two cases are similar to above case if (d3 == d4 && 2 * d3 == d2 && 2 * distSq(p3, p2) == distSq(p3, p4)) { return true; } if (d2 == d4 && 2 * d2 == d3 && 2 * distSq(p2, p3) == distSq(p2, p4)) { return true; } return false; } public static void main(String[] args) { Point p1 = new Point(20, 10), p2 = new Point( 10, 20 ), p3 = new Point(20, 20 ), p4 = new Point( 10, 10 ); System.out.println(isSquare(p1, p2, p3, p4)==true ? "Yes four points forms a square" : "No four points don't forms a square"); } }

class Square { // Structure of a point in 2D space static class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } }; // A utility function to find square of distance // from point 'p' to point 'q' static int distSq(Point p, Point q) { return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y); } // This function returns true if (p1, p2, p3, p4) form a // square, otherwise false static boolean isSquare(Point p1, Point p2, Point p3, Point p4) { int d2 = distSq(p1, p2); // from p1 to p2 int d3 = distSq(p1, p3); // from p1 to p3 int d4 = distSq(p1, p4); // from p1 to p4 if (d2 == 0 || d3 == 0 || d4 == 0) return false;

+ info

ADVANTAGES, DISADVANTAGES AND LIMITATIONS

The advantages of the program are: It is simple and easy to understand It uses a HashSet to avoid duplicate calculations of distances It uses a mathematical property of squares to check the validity of the points The disadvantages of the program are: It assumes that the points are given in integer coordinates and does not handle floating-point values It does not handle the case when the points are collinear or coincident It does not handle the case when the points are given in a different order than the expected one

The limitations of the program are: It can only check if four points form a square and not any other shape It can only work with two-dimensional points and not higher dimensions It can only handle a small range of values and not very large or very small numbers

+ info