pdf:請看pE
https://drive.google.com/file/d/1OPQBuMYzQWblmuyJDCk5TYc9RJqR8WbA/view?usp=sharing
你的朋友東納德的別墅外有兩層圍籬，他想要計算在這兩層圍籬之間的土地面積。他能測量圍籬的長度，但他對計算面積毫無概念。東納德的朋友華生發現圍籬可能是由專精於計算幾何的電腦科學家建造的，因為下列事實絕非巧合：
• 外層圍籬之內的土地，形成一個完美的圓形$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 ≤ T ≤ 100 $
• $3 ≤ n ≤ 10 $
• $10 ≤ c ≤ 1000 $
• $ℓ_1, ..., ℓ_n > 0 $
• $P$ 必在圓 $C$ 內部。
對每筆測試資料，請輸出兩層圍籬間的⼟地⾯積。
相對或絕對誤差小於$10^{-6}$就算正確。也就是說，如果你的答案是$a$，裁判的答案是$b$，若且唯若$\frac{|a-b|}{max(1,|b|)}≤10^{-6}$你的答案會被視為正確。
2 10.0 3 1 1 1 10.0 4 1 1 1 1
7.524734452702549 6.9577471545947684
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||