Texas Trip

Time limit1sMemory limit128 MB

Summary

Given up to 30 lattice points per test case, find the area of the smallest square (any rotation) that covers all of them, printed to two decimals.

Level: Medium7 of 10
Topics: Geometry, Binary search, Brute force, Math
Solved: No attempts yet

Problem

After a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes punched into the door of his SUV. The local tire store only sells fiberglass patching material in square sheets. What is the area of the smallest square patch Harry needs to repair his door?

The holes are given as points on the integer lattice in the plane. Find the area of the smallest square that covers all of the holes. The square may be rotated to any orientation; it does not have to be axis-aligned.

Input

The first line contains a single integer $T$ , the number of test cases that follow. Each test case is then given in turn.

Each test case begins with a line containing a single integer $n$ , the number of points. Each of the next $n$ lines contains two integers $x$ and $y$ , the coordinates of one point.

You are guaranteed that $T \le 30$ and that no test case contains more than $30$ points. Every point lies at a distance of at most $500$ from the origin $(0,0)$ . All integers are given in decimal with no leading zeroes.

Output

For each test case, print the area of the smallest square that covers all of its points on its own line, with exactly two digits after the decimal point.

Examples4

Example 1

Input

Expected output

4.00
242.00

Example 2
Input
```
1
1
5 5
```
Expected output
```
0.00
```
Example 3
Input
```
1
2
0 0
2 0
```
Expected output
```
2.00
```
Example 4
Input
```
1
4
-15 -5
15 -5
15 5
-15 5
```
Expected output
```
800.00
```