18150번 - Largest Quadrilateral 다국어

Given some points on a 2D Euclidean plane, please calculate the maximum area of quadrilaterals with vertices in given points. For example, points A(0, 0), B(1, 0), C(3, 1), D(1, 2), E(0, 1) are given. These points form 5 simple quadrilaterals ABCD, ABCE, ABDE, ACDE, BCDE with areas 3, 2, 1.5, 3, 3 respectively and 10 complex quadrilaterals ABDC, ABEC, ABED, ACED, BCED, ACBD, ACBE, ADBE, ADCE, BDCE with smaller areas. So the maximum area is 3.

Figure 4: BCDE has the maximum area 3 among all quadrilaterals.

Please notice that duplicated points may appear in the given points. All the degenerate cases are also taken as quadrilaterals such as quadrilateral ABCD with A(0, 0), B(0, 0), C(0, 0), D(0, 0).

The first line is an integer T indicating the number of test cases. The first line of each test case contains an integer N followed by N lines. Each line of the following N lines contains two integers X and Y representing a point (X, Y ).

For each test case, please output the maximum area among all quadrilaterals with vertices in given points.

• 1 ≤ T ≤ 3
• 4 ≤ N ≤ 4096
• 0 ≤ X ≤ 10⁹
• 0 ≤ Y ≤ 10⁹
• You may not output numbers with scientific notaions. I.e., outputting 3E8 for 300000000 is not allowed.
• The area must be outputted without any redundant characters. I.e., outputting 3.0 for 3 is incorrect.