Cities in a country

4

1 votes
Greedy algorithm, approved, Data Structures, Algorithms, Easy, Open, Greedy algorithm, Greedy algorithm
Problem

There are N cities in a country. The cities are specified by the Cartesian coordinates. Each city is located at a point that contains integer coordinates. You are required to create a boundary that encloses all the cities. The boundary must be in the shape of a square and parallel to the coordinate axes.

Your task is to determine the minimum area that is enclosed by the created boundary such that cities are located on or inside the boundary.

Input format

  • First line: T denoting the number of test cases
  • Next T lines: A single positive integer N denoting the number of cities in your country
  • Next N lines: Two integers xi and yi denoting the coordinates of the ith city

Output format

For each test case, print a single non-negative integer denoting the minimum area of the square boundary that encloses all the cities inside or on its boundary.

Constraints

1T5

1N105

109xi,yi109

Sample Input
2
4
-1 -1
1 1
1 -1
-1 1
3
0 0
1 1
2 2
Sample Output
4
4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, all the points are on the boundary of a square of side 2. Hence answer=4.

In the second test case, the smallest square can be drawn is of side 2 having center at (0,0).

Editor Image

?