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.

code

--

--

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