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.

2 Likes