Golf Field

Professor Octopus owns a large field that used to be a golf course. The field still has many holes where golf balls used to sink. Professor Octopus offers to sell you a part of the field at a fixed price. The part is decided like this: you choose four holes in the field, and you get the part of the field bounded by the convex hull of the chosen holes. The convex hull of the chosen holes is the smallest convex polygon that contains every chosen hole in its interior or on its boundary. The field is of uniform quality, so you want to choose four holes whose convex hull has the largest area.

Figure 1

For example, Figure 1 (a) shows eight holes in a field. Suppose you chose the four holes 1, 3, 5 and 8, drawn as black points. No quadrilateral with corners at those four holes is convex, so the convex hull of the four holes is the triangle with corners at holes 1, 3 and 8 shown in the figure. It is not hard to see that this triangle is also the largest convex hull that any four of the holes can give. Figure 1 (b) shows another field with eight holes. There the largest convex hull is the convex quadrilateral with corners at holes 1, 3, 5 and 8.

Given a set $P$ of $n$ points in the plane, compute the largest area of a convex hull determined by four points of $P$.

Your program reads from standard input. The input consists of $T$ test cases, and the first line holds $T$. Each test case starts with a line containing an integer $n$, the number of points of the set $P$, where $4 \le n \le 30000$. The next line contains a sequence of $2n$ integers $x_1\ y_1\ x_2\ y_2 \dots x_n\ y_n$, where $x_i$ and $y_i$ are the x-coordinate and the y-coordinate of the point $p_i$ of $P$. The coordinates are all integers with $-10^9 \le x_i \le 10^9$ and $-10^9 \le y_i \le 10^9$. No three or more points lie on one line.

Your program writes to standard output. For each test case, print on its own line the largest area of a convex hull determined by four points of $P$, with one digit after the decimal point. All coordinates are integers, so the area is always a multiple of $0.5$ and the digit after the decimal point is 0 or 5.