In this HackerEarth Protect the Cities problem solution There are N cities in Imaginary Land. The President of Imaginary Land uses the Cartesian coordinates. Each city is located at some point with integer coordinates. The President is very careful and concerned about the well-being of the citizens of his country.
For that reason, he wants to create a boundary and cover all the cities inside that boundary. The boundary should be in the shape of a square and should be parallel to the coordinate axes. Find the minimum area enclosed by the boundary such that all the cities are on or inside the boundary.
HackerEarth Protect the Cities problem solution.
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n;
cin >> n;
long long int x[n + 1], y[n + 1];
for(int i = 0; i < n; i++)
cin >> x[i] >> y[i];
long long int maxx, maxy;
long long int minx, miny;
maxx = maxy = (long long)(-1e18);
minx = miny = (long long)(1e18);
for(int i=0;i<n;i++)
{
maxx = max(maxx, x[i]);
minx = min(minx, x[i]);
maxy = max(maxy, y[i]);
miny = min(miny, y[i]);
}
long long ans = max(maxx - minx, maxy - miny);
ans *= ans;
cout << ans << endl;
return 0;
}