星辰大海

题目背景

Entering the unknown,

Sending all the poets to the stars.

Daring to see beyond the manmade,

Woe to you who evade the horizon.

题目描述

小X的姐姐小F是一名X国的占星师。

星象的观察对于魔法师们来说是必不可少的，在X国占星师的研究下，一共有$N$颗「星」已经被发现了。占星师们认为，可能存在「星」的天空是一片大小有限的平面，其中每一个点的纵坐标和横坐标的绝对值均不超过$10^6$，每一颗被已经被发现的「星」都存在一个坐标$P_i(x_i,y_i)$，它们的坐标是两两不同的。

每三颗「星」$(i,j,k)\ (i\ne j,i\ne k,j\ne k)$之间都会存在一个有向的角度$\angle P_iP_jP_k$，其中$\angle P_iP_jP_k\in(-\pi,\pi]$，其符号分为正、负、零三种。「星」之间的角度变化会带来星象性质的改变，当任意三颗「星」之间所成的有向角度的符号变化的时候，星象的性质都会有不同程度的变化。

最近，小F发现，编号为$1$的「星」从原本被观测到的位置消失了，但此时，星象的性质并没有发生变化。小F想要借此来估算编号为$1$的「星」可能去往的区域的大小，从而重新找到它的位置，你的任务就是帮助小F计算这个大小。

输入格式

第一行一个整数$Num$，表示测试点编号，以便选手方便地获得部分分，你可能不需要用到这则信息，样例中$Num$的含义为数据范围与某个测试点相同。

接下来一行一个整数$T$，表示测试数据的组数。

对于每一组测试数据，第一行一个整数$N$，表示「星」的个数。

接下来$N$行，每行两个整数$x_i,y_i$，表示一颗星的位置。

输出格式

对于每组测试数据，输出一行一个实数$Ans$，表示编号为$1$的「星」可能去往的区域的大小。

你的答案将被视为正确，当且仅当其与标准答案的绝对或相对误差不超过$10^{-6}$。

样例1输入

4
4
4
1 1
0 0
2 0
1 2
3
1 0
0 0
2 0
3
1 1
0 0
2 0
5
0 5
0 0
1 10
5 15
-5 15

样例1输出

2.0000000000
0.0000000000
2000000000000.0000000000
13.3823529412

样例1解释

在第$1$组测试数据中，所求的区域即为$\triangle P_2P_3P_4$，其面积为$2$。

在第$2$组测试数据中，所求的区域为$P_2$和$P_3$连线的所在直线，其面积为$0$。

在第$3$组测试数据中，所求的区域为第一、二象限，考虑到可能存在「星」的天空的大小限制，其面积为$2\times10^{12}$。

样例2

见下发文件ex_everdream2.in，ex_everdream2.out

样例3

见下发文件ex_everdream3.in，ex_everdream3.out

点此下载

数据范围与约定

对于所有测试数据，保证$1\leq T\leq 1000$，$3\leq N,\sum N\leq 5\times10^5$，$|x_i|,|y_i|\leq 10^6$。

保证「星」的坐标两两不同。

特殊性质中的「凸多边形」指各内角均不超过$\pi$的简单多边形。

详细的数据范围见下表。

提示

如果你希望通过全部的测试点，建议使用精度较高的数据类型。