1319 . 技能選擇 Skillpoints
TopCoder
Description
如果你沒有玩過皮卡恩打桌球，至少你也要玩過卡恩歷險記；
如果你沒有玩過卡恩歷險記，至少你也要把這題給AC！
不妨假設你是個很威的電玩人物卡恩，
目前經過一番激烈的戰鬥，砍殺了無數隻怪物，你有若k點技能點可供使用
而你有n項不同的技能(好威桌球殺球、瞬間秒殺法、小品演算法……)，分別編號為s1、s2、s3、…、sn。
我們可以把你的技能分布畫成圖。
做圖方法是以一個中心畫出n條線，相鄰兩條之間的夾角相同。
而每條線就代表一項技能，這些線依順時針順序是L1, L2, …, Ln
而我們依照si的點數在Li上面做點Pi，且Pi到中心的距離就是si之點數。
將所有點Pi依序連起來，得到一個多邊形P，定義你這個人物的「強度」，就是P的面積。
(敘述十分難懂，可以可參考一下上圖。圖中強度就是陰影部分的面積。注意到s1和s5是相鄰的)
現給定n、k，以及目前各個技能的點數依序為s1、s2、s3、…、sn
試求將k點技能點使用在這n項技能上後，你的強度最多可以變成原來的多少倍？(可假設技能是沒有上限的！)
當然，一點技能點可以使一項技能等級增加1
而你並不能將一點技能點拆開來用，例如用在A技能0.4，用在B技能0.6
我想這些常識不必多提
請輸出到小數後第四位
Input Format
第一行有一個整數t，代表有幾組測資
每組的第一行有兩個整數n和k，依序代表有幾項技能、以及可供使用的技能點
接下來一行有n個數，代表每項技能目前的點數
技能數目4<=n<=100,000
可用技能點數0<=k<=5,000,000
目前點數1<=si<=5,000,000
Output Format
請輸出一個小數，四捨五入至小數點後四位，代表最多可以變為原先強度的多少倍?
Sample Input 1
6 4
2 2 2 3 1 3
Sample Output 1
Hints
2019/03/31 測資修正
Problem Source
原TIOJ1319 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 8 |
| 2 | 1 | 8 |
| 3 | 2 | 8 |
| 4 | 3 | 8 |
| 5 | 4 | 8 |
| 6 | 5 | 8 |
| 7 | 6 | 8 |
| 8 | 7 | 8 |
| 9 | 8 | 8 |
| 10 | 9 | 8 |
| 11 | 10 | 8 |
| 12 | 11 | 12 |