Minimum area of a square enclosing given set of points

Problem solving with programming: 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.

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.

cin >> n;


int i,x,y;


cin >> x >> y;


long long min_x = x, max_x = x;


long long min_y = y, max_y = y;


for( i = 1; i < n; i++ )


{


cin >> x >> y;


if( x < min_x)


min_x = x;


else if( x > max_x )


max_x = x;




if( y < min_y )


min_y = y;


else if( y > max_y )


max_y = y;


}


long long side = max_x - min_x;


if( side < max_y-min_y )


side = max_y-min_y;


cout << side*side << endl;

Read full article from Problem solving with programming: Minimum area of a square enclosing given set of points