텍사스 여행

시간 제한1초메모리 제한128 MB

요약

각 테스트 케이스마다 30개 이하의 격자점이 주어질 때, 회전을 허용한 가장 작은 정사각형의 넓이를 소수점 둘째 자리까지 구한다.

난이도: 보통10점 중 7점
유형: 기하, 이분 탐색, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

해리는 친구 딕과 함께 하루 동안 여행을 다녀온 뒤, 자신의 SUV 문에 작은 구멍들이 이상한 모양으로 뚫려 있는 것을 발견했습니다. 동네 타이어 가게에서는 구멍을 때울 유리섬유 보수재를 정사각형 시트 형태로만 판매합니다. 해리가 문을 수리하는 데 필요한 가장 작은 정사각형 보수재의 넓이는 얼마일까요?

구멍은 평면의 정수 격자점으로 주어집니다. 모든 구멍(점)을 덮는 가장 작은 정사각형의 넓이를 구하세요. 이때 정사각형은 임의의 방향으로 회전할 수 있으며, 반드시 좌표축에 평행할 필요는 없습니다.

입력

첫 번째 줄에는 이어지는 테스트 케이스의 개수를 나타내는 정수 $T$ 가 주어집니다. 그 뒤로 각 테스트 케이스가 차례로 이어집니다.

각 테스트 케이스는 점의 개수를 나타내는 정수 $n$ 이 적힌 줄로 시작하며, 이어지는 $n$ 개의 줄에는 각각 한 점의 좌표를 나타내는 두 정수 $x$ 와 $y$ 가 주어집니다.

$T \le 30$ 이고, 어떤 테스트 케이스도 점을 $30$ 개보다 많이 포함하지 않습니다. 모든 점은 원점 $(0,0)$ 으로부터 거리가 $500$ 을 넘지 않는 위치에 있습니다. 모든 정수는 앞에 $0$ 이 붙지 않은 십진수로 주어집니다.

출력

각 테스트 케이스마다, 모든 점을 덮는 가장 작은 정사각형의 넓이를 한 줄에 하나씩, 소수점 아래 정확히 두 자리까지 출력하세요.

예제4

예제 1

입력

예상 출력

4.00
242.00

예제 2
입력
```
1
1
5 5
```
예상 출력
```
0.00
```
예제 3
입력
```
1
2
0 0
2 0
```
예상 출력
```
2.00
```
예제 4
입력
```
1
4
-15 -5
15 -5
15 5
-15 5
```
예상 출력
```
800.00
```