시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
9 초 512 MB 20 1 1 5.000%

문제

Given n points on the plane, namely (x1, y1), (x2, y2), ..., (xn, yn), your problem is to write a computer program that constructs a quadrilateral Q that satisfies all of the following conditions.

  1. Each of the four sides of Q must pass through at least two of the n given points.
  2. Q must be convex.
  3. All of the n points must be inside Q or on Q.
  4. Among all quadrilaterals satisfying (1) to (3), Q must have minimum area. It is possible that such quadrilateral is not unique; there may be several such quadrilaterals with minimum area. Your program should compute the value of this minimum area.

입력

The first line of input contains a single integer T indicating the number of data sets. The following lines describe the data sets.

The first line of each data set will contain a single integer n. This is followed by n lines, the i th line of which contains xi and yi separated by a space, the (real-valued) x- and y-coordinates of the i th point, respectively.

  • Constraints
  • 1 ≤ T ≤ 60
  • 1 ≤ n ≤ 300
  • |xi|,|yi| ≤ 1000.00
  • Coordinates are given with at most two decimal places.
  • The points are distinct.

출력

For each data set, print a single line containing the minimum area, if such a quadrilateral exists. Otherwise print “none” (without quotes). Your answer should be accurate to within an absolute error of 10−6 from the correct answer.

예제 입력 1

2
9
0 1
1 0
1 3
1 5
3 1
3 3
5 0
5 2
6 4
4
-1 -1
5 -1
0 0
-1 51

예제 출력 1

23.625
none