Find number of squares from N points

I love mathematics πŸ’—

So,Today morning I decided to solve mathematical problem.

Identify all square from given N points.

lets first store points in vector

const int limit=10000

vector < int > points[limit]

assume point is (x,y)

points[x].push_back( y)

in points vector we are keeping all points having same x coordinate .

now sort every points vector by y coordinate

for each possible x coordinate

sort( points[x].begin() , points[x].end())

how we check point (x,y) exist

bool exists(int x, int y) {

if (x > upperLimit) return false

return binary_search(points[x], y)


now we will write function to check square is identified previously or not to avoid duplicacy in answer.

we can store diagonal points in map

map[{x1,y1}, {x2, y2}] = 1

Then for each pair of points from vector points

lets it be (k, y 1) and (k, y 2)

check: is there squere that contain them as vertexes. So we should check: is there(in input) pair of points (k β€” |y 2 β€” y 1|, y 1) and (k β€” |y 2 β€” y 1|, y 2), or pair (k + |y 2 β€” y 1|, y 1) and (k + |y 2 β€” y 1|, y 2).

if square exist then we check in map is it already counted in answer if not then we will increment the answer and add this square into map.

finally solved.




Feed me code

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store