시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 1024 MB | 58 | 23 | 16 | 42.105% |
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.
3 5 0 0 1 0 3 1 1 2 0 1 4 0 0 4 0 0 4 1 1 4 0 0 1 1 2 2 1 1
3 6 0
1 4 0 0 1 0 0 1 3 2
2.5