Problem:
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <climits> | |
| using namespace std; | |
| int main() | |
| { | |
| int n; | |
| 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; | |
| return 0; | |
| } |
by