Codechef Count the squares problem

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.

https://www.codechef.com/viewsolution/3967921

2 Likes