Homework

As this term is going to end, DRD needs to start his graphical homework.

In his homework, DRD needs to partition a point set $S$ into two part. You can see that if one part has 100 points and the other has only 1 point, then this partition cannot be beautiful since it's too imbalanced. DRD wants to find a line to separate $S$, so that no points lie in the line and there are at least $\lfloor \frac{|S|}{3}\rfloor$ points in each side of the line. DRD finds it amazing that there may exist some points (no need to be in $S$) that if a line $l$ passes it and does not pass any points in $S$, then $l$ can be a separating line. Now, he wonders the area these points form.

First line: a positive integer $T \leq 10$ indicating the number of test cases.
There are $T$ cases following. In each case, the first line contains an positive integer $n \leq 1000$, and $n$ lines follow. In each of these lines, there are 2 integers $x_i, y_i$ indicating a point $(x_i, y_i)$ in the plane. Note that $|x_i|, |y_i| \leq 10^4$
You can assume that no three points in $S$ lies in the same line.

For each test case: output ''Case #x: ans'' (without quotes), where $x$ is the number of the cases, and $ans$ is the area these points form.
Your answer is considered correct if and only if the absolute error or the relative error is smaller than $10^{-6}$.

2
4
1 1
1 -1
-1 -1
-1 1
8
-1 -1
-1 1
1 -1
1 1
-2 -2
-2 2
2 -2
2 2

Case #1: 4.000000
Case #2: 5.333333

The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest