Friday, February 13, 2015

Minimum area of a square enclosing given set of points

Given a set of coordinates in a two dimensional plane, How do we find the area of a minimum square which includes all the points. The points can exist on the border also.

For example consider two points (0,0), (1,2) we need a minimum 2*2 square to cover these points. Hence the area is 4.

Similarly if the input coordinates are (-1,1), (1,3), (0,2) we need 2*2 square.

This is a problem from Codeforces. Click here to read the problem statement and solve it on your own.

Here is the solution approach. We iterate through all the points and keep track of the maximum and minimum of x and y-coordinates. Lets assume min_x is the left most x-coordinate, and max_x is the right most x-coordinate among all the points. The difference between these two gives the minimum width required.

Similarly the difference between min_y and max_y gives the minimum height required. So to accommodate all the points, we need a square of size which is the maximum of these two differences.

Below is the C++ implementation of the above algorithm.