Impromptu Outdoor Gallery

The artist Cody-Jamal recently decided to out-hip all of his hipster friends by showing his latest paintings in an impromptu outdoor gallery. He is going to show up in a field, put up some paintings, and display them.

The field has $N$ posts in it, and no three of them are collinear (which also means that no two posts are in the same place). Cody-Jamal is going to choose four of them, in order, and call them $p_1, p_2, p_3$, and $p_4$. He will then string velvet ropes between $p_1$ and $p_2$, $p_2$ and $p_3$, $p_3$ and $p_4$, and finally $p_4$ and $p_1$. He must choose the four ordered posts so that no two ropes cross. In other words, $p_1p_2p_3p_4$ must be a simple quadrilateral. The quadrilateral may be convex or concave. He will then hang his paintings inside the region enclosed by the ropes.

To attract wealthy art lovers who might buy his paintings, Cody-Jamal is hiring waitstaff to walk around and serve refreshments to visitors. The cost of the refreshments is fixed, but the cost of the waitstaff is proportional to the area they have to walk. They charge 2 artcoins per square meter. Therefore, Cody-Jamal wants to choose $p_1, p_2, p_3$, and $p_4$ to minimize the area of the quadrilateral $p_1p_2p_3p_4$, and so minimize the cost (in artcoins) of the refreshment service. What is this minimum cost?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing a single integer $N$, the number of posts in the field. $N$ more lines follow. The $i$-th of them contains two integers $X_i$ and $Y_i$: the coordinates of the $i$-th post, in meters from an arbitrary origin.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of artcoins Cody-Jamal has to pay. In other words, y is twice the area (in square meters) of a smallest simple quadrilateral that has four of the input points as vertices. This value is always an integer.

• $1 \le T \le 100$
• $4 \le N \le 1000$
• $-10^9 \le X_i \le 10^9$ for all $i$.
• $-10^9 \le Y_i \le 10^9$ for all $i$.
• No three points in the input are collinear.

In Case #1, there are only 4 points in the input, and every ordering that forms a simple quadrilateral gives a square with side length 10.

In Cases #2 and #3, an optimal choice is to leave out the first point and use the last four, in the order given in the input.