How to solve the problem Count the squares https://www.codechef.com/problems/D6/
please explain the logic
How to solve the problem Count the squares https://www.codechef.com/problems/D6/
please explain the logic
Since the number of points are small (N = 500), we can iterate through each pair of points C1(X1, Y1) and C2(X2, Y2) and assuming C1 - C2 to be a side of a possible square, we can generate 2 other pairs C3(X3, Y3) and C4(X4, Y4) such that C1, C2, C3, C4 make a square. We can then check whether C3 and C4 exist in our set or not.
In this way, we will count each square 4 times (1 time for each side), so answer would be count / 4.
You can refer to the following solution, for the above approach.