Given lower left and upper right coordinates (x1, y1) and (x2, y2) of a square, the task is to count the number of integral coordinates that lies strictly inside the square.
Examples:
Input: x1 = 1, y1 = 1, x2 = 5, x3 = 5
Output: 9
Explanation:
Below is the square for the given coordinates:
Input: x1 = 1, y1 = 1, x2 = 4, x3 = 4
Output: 4
Approach: The difference between the x and y ordinates of the lower and upper right coordinates of the given squares gives the number integral points of x ordinates and y ordinates between opposite sides of square respectively. The total number of points that strictly lies inside the square is given by:
count = (x2 – x1 – 1) * (y2 – y1 – 1)
For Example:
In the above figure:
1. The total number of integral points inside base of the square is (x2 – x1 – 1).
2. The total number of integral points inside height of the square is (y2 – y1 – 1).
These (x2 – x1 – 1) integrals points parallel to the base of the square repeats (y2 – y1 – 1) number of times. Therefore the total number of integral points is given by (x2 – x1 – 1)*(y2 – y1 – 1).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the integral// points inside a squarevoid countIntgralPoints(int x1, int y1, int x2, int y2){ cout << (y2 - y1 - 1) * (x2 - x1 - 1);}// Driver Codeint main(){ int x1 = 1, y1 = 1; int x2 = 4, y2 = 4; countIntgralPoints(x1, y1, x2, y2); return 0;} |
Java
// Java program for the above approachclass GFG {// Function to calculate the integral // points inside a square static void countIntgralPoints(int x1, int y1, int x2, int y2){ System.out.println((y2 - y1 - 1) * (x2 - x1 - 1));}// Driver Codepublic static void main(String args[]){ int x1 = 1, y1 = 1; int x2 = 4, y2 = 4; countIntgralPoints(x1, y1, x2, y2);}}// This code is contributed by rutvik_56 |
Python3
# Python3 program for the above approach# Function to calculate the integral# points inside a squaredef countIntgralPoints(x1, y1, x2, y2): print((y2 - y1 - 1) * (x2 - x1 - 1))# Driver Codeif __name__ == '__main__': x1 = 1 y1 = 1 x2 = 4 y2 = 4 countIntgralPoints(x1, y1, x2, y2)# This code is contributed by Samarth |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate the integral // points inside a square static void countIntgralPoints(int x1, int y1, int x2, int y2) { Console.WriteLine((y2 - y1 - 1) * (x2 - x1 - 1)); } // Driver codestatic void Main(){ int x1 = 1, y1 = 1; int x2 = 4, y2 = 4; countIntgralPoints(x1, y1, x2, y2); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for the above approach// Function to calculate the integral// points inside a squarefunction countIntgralPoints(x1, y1, x2, y2){ document.write( (y2 - y1 - 1) * (x2 - x1 - 1));}// Driver Codevar x1 = 1, y1 = 1;var x2 = 4, y2 = 4;countIntgralPoints(x1, y1, x2, y2);</script> |
4
Time Complexity: O(1), as we are not using any loops.
Auxiliary Space: O(1), as we are not using any extra space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
