Hi, I stumbled across a simple question:
Given $$$4 \le N \le 1000$$$ points on a cartesian plane, count the number of squares where the corner of each squares lie on the points.
The first obvious method would be to put all the points in a map, and perform an $$$O(N^3)$$$ solution to find the last corner point and see if it exists.
The next method would be to find opposite corner points in $$$O(N^2)$$$ time and check if the rest of the two points exist.
Lastly, I was wondering if there's an $$$O(N\log N)$$$ solution or $$$O(N)$$$ solution?