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.
