SHAMAN - Shamans

no tags 

In the far bare land there lives a mysterious tribe. They suffer from drought every year but they stick to their faith in god that they will never leave their home land. To counter the dry weather the shamans in the tribe must pray during the hard time and hope the blessed rain will aid their production of food.

There are 4 chief shamans in the tribe and each of them will choose a summit in the territory to proceed with his praying. The area in which the shamans' spells take effect will be the quadrangle they form, each of them being one of its vertices (which the god will see when he looks down from the high heavens). The land is quite full of pinch and punch and the tribe has selected quite a few peaks for the shamans to pray on. Of course the area of the quadrangle is expected to be as large as possible so before the shamans actually go out, they will have to choose the 4 peaks that best suit their purpose.

Input

One integer in the first line, stating the number of test cases, followed by a blank line. There will be not more than 80 tests.

For each test case, the first line is an integer n (4 <= n <= 2000) stating the number of peaks. Then n lines follow, each presenting the position of a peak, with two integers x, y (-20000 <= x, y <= 20000).

The test cases will be separated by a single blank line.

Output

A floating point number with exactly 1 digit precision: the maximum area the shamans can cover.

Example

Input:
2

4
0 0
1 0
1 1
0 1

4
0 0
0 1
1 1
1 0

Output:
1.0
1.0

hide comments
Mercury: 2015-01-09 23:45:04

is there blank line after every test case ?

[Rampage] Blue.Mary: 2010-10-11 00:25:32

Weak test data. See (newly added) problem DRAWQUAD.

Tony Beta Lambda: 2009-08-19 09:33:35

If the shamans form a concave quadrangle, the correct answer will be the area of its convex hull. That is, for input
4
0 2
2 -2
-2 -2
-1 -1
the output should be
8.0


Added by:Neal Zane
Date:2004-11-02
Time limit:0.571s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Neal Zane