3423. 圍籬

单点时限: 3.0 sec

内存限制: 256 MB

你的朋友東納德的別墅外有兩層圍籬,他想要計算在這兩層圍籬之間的土地面積。他能測量圍籬的長度,但他對計算面積毫無概念。東納德的朋友華生發現圍籬可能是由專精於計算幾何的電腦科學家建造的,因為下列事實絕非巧合:

  • 外層圍籬之內的土地,形成一個完美的圓形 $C$。以下用 $B$ 代表 $C$ 邊界上的所有點所形成的集合。
  • 內層圍籬之內的土地,形成一個非自交 $n$ 邊形 $P$,即不共用頂點的兩條邊,沒有交點。以下用 $V$ 代表 $P$ 的所有頂點所形成的集合。
  • $P$ 所有頂點到 $C$ 的最短距離都是一樣的,即對 $V$ 中相異的兩頂點 $(x_u,y_u),(x_v,y_v)$,下述等式成立:

$$\min_{(x,y)\in B}\sqrt{(x-x_u)^2+(y-y_u)^2}=\min_{(x,y)\in B}\sqrt{(x-x_v)^2+(y-y_v)^2}.$$

你恍然大悟。你明白了如何由外層圍籬總長 $c$ 以及內層圍籬的 $n$ 個邊長 $\ell_1,\dots,\ell_n$ 計算出兩個圍籬之間的土地面積。還記得東納德知道如何測量圍籬長度吧?請幫他算出面積吧。

输入格式

輸入的第一行有一個正整數 $T$ 代表有多少筆測試資料。每一筆測試資料有兩行,第一行有兩個數字 $c$ 跟 $n$,以一個空白隔開。$c$ 代表了外層圍籬的總長,也就是 $C$ 的周長。$n$ 代表內層圍籬的頂點數目。
第二行有 $n$ 個正整數 $\ell_1,\dots,\ell_n$,代表 $n$ 邊形 $P$ 的各個邊長。

可假設

  • $1 \le T \le 100$
  • $3 \le n \le 10$
  • $10 \le c \le 1000$
  • $\ell_1,\dots,\ell_n>0$
  • $P$ 必在圓 $C$ 內部。

输出格式

對每筆測試資料,請輸出兩層圍籬間的土地面積。只要絕對或相對誤差小於 $10^{-6}$ 就會被視為正確。

样例

Input
2
10.0 3
1 1 1
10.0 4
1 1 1 1
Output
7.524734452702549
6.9577471545947684

1 人解决,3 人已尝试。

1 份提交通过,共有 7 份提交。

9.9 EMB 奖励。

创建: 7 年前.

修改: 7 年前.

最后提交: 3 年,12 月前.

来源: TOPC 2017

题目标签