Little Cyan Fish muốn tô màu $n$ điểm bằng màu xanh lơ (cyan) hoặc màu trắng. Điểm thứ $i$ nằm tại tọa độ $(x_i, y_i)$. Các điểm này đôi một phân biệt và là các đỉnh của một đa giác lồi chặt, được liệt kê theo thứ tự ngược chiều kim đồng hồ.

Gọi $H_c$ là bao lồi của các điểm màu xanh lơ, và gọi $H_w$ là bao lồi của các điểm màu trắng. Bao lồi là tập lồi nhỏ nhất chứa các điểm đã cho. Bao lồi của một tập rỗng là tập rỗng; bao lồi chỉ gồm một điểm hoặc một đoạn thẳng có diện tích bằng không.

Hãy tìm diện tích lớn nhất có thể của $H_c \cap H_w$, tức là phần miền chung của hai bao lồi.

Minh họa cho hai bộ dữ liệu đầu tiên trong ví dụ (bộ thứ nhất ở bên trái, bộ thứ hai ở bên phải).

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^4$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($3 \le n \le 10^5$), cho biết số lượng điểm. Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $x_i$ và $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), cho biết tọa độ của điểm thứ $i$.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số thực, cho biết diện tích lớn nhất có thể của phần giao của hai bao lồi.

Câu trả lời của bạn sẽ được chấp nhận nếu sai số tuyệt đối hoặc tương đối của nó không vượt quá $10^{-8}$. Một cách hình thức, gọi kết quả của bạn là $a$ và đáp án của ban giám khảo là $b$; kết quả của bạn được chấp nhận khi và chỉ khi $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Ví dụ

Dữ liệu vào 1

3
7
0 0
3 0
4 1
3 3
1 4
-1 3
-1 1
5
0 0
2 0
3 1
1 3
-1 1
7
-1000000000 -1000000000
-500000001 -500000002
499999998 499999995
999999998 999999994
500000000 499999997
-499999999 -500000000
-999999999 -999999999

Dữ liệu ra 1

5.944444444444444444
0
2.458333333333333404

Ghi chú

Trong bộ dữ liệu ví dụ đầu tiên, Little Cyan Fish tô màu các điểm $1$, $2$, $4$ và $6$ màu xanh lơ, và các điểm còn lại màu trắng. Tứ giác màu xanh lơ và tam giác màu trắng giao nhau trên một miền có diện tích $\frac{107}{18}$, đây là diện tích lớn nhất có thể.

Trong bộ dữ liệu ví dụ thứ hai, ít nhất một màu có tối đa hai điểm, vì vậy phần giao có diện tích bằng không. Hình vẽ minh họa trường hợp các điểm $1$, $3$ và $5$ được tô màu xanh lơ; bao lồi màu trắng là đoạn thẳng nối hai điểm $2$ và $4$.

Trong bộ dữ liệu ví dụ thứ ba, việc tô màu các điểm $1$, $4$ và $6$ màu xanh lơ và các điểm còn lại màu trắng mang lại diện tích phần giao lớn nhất là $\frac{59}{24}$.