Let us say that we are N integer coordinates (x, y) - what would our approach be if we were supposed to find the number of squares we could make from those given n points?
Additionally, if we were to figure out how many, minimally, more points should we add that we manage to form at least ONE square from the points, how would we go about that?
On
I dont have the reputation to comment so I am writing it in answer. This problem seems to be taken from http://www.codechef.com/OCT14/problems/CHEFSQUA live contest! please do remove it. Please respect the code of honor.
And more over you are complaining of no help.
You could iterate over all pairs of points $(x_1,y_1), (x_2,y_2)$, rotate the difference vector by 90° and add that rotated difference to either point to obtain two more points which would form a square:
\begin{align*} x_3 &= x_1 + (y_2 - y_1) & x_4 &= x_2 + (y_2 - y_1) \\ y_3 &= y_1 + (x_1 - x_2) & y_4 &= y_2 + (x_1 - x_2) \end{align*}
Check whether these extra points $(x_3,y_3)$ and $(x_4,y_4)$ are contained in your input. Make sure you iterate over ordered pairs, i.e. for every pair of distinct points, do the above computation for both possible orders, so that you get the squares on either side of the line joining these. In the end, you'd have counted each square four times (once for every edge), so divide the total count by four.
This can be adapted to check whether there are any squares which lack only a single point, so it can be used to determine the number of points you have to add to form at least one square.
The above approach might be far from efficient, but if you are looking for efficient algorithms, you might be better off asking on Stack Overflow. There is very little math in this question, and a lot of algorithm.