TopCoder

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

33.3% (1/3)

Tags

Description

小波有一個城堡,城堡的範圍在二維平面上會是一個圓形,圓形的中心在 $(x_c, y_c)$ 且半徑為 $r_c$。小波每天都在他的城堡過著快樂的日子。

小奕因為不喜歡小波所以想要攻擊小波的城堡。他有 $N$ 種魔法可以施放,其中施放第 $i$ 種魔法會在一個小波城堡以外的座標 $(x_i, y_i)$ 上生成出一個血量為 $h_i$ 的士兵。士兵在生成後會以每秒 1 單位距離的速度往小波城堡的圓心移動。而在走到城堡的邊界後,士兵就會停止移動並開始攻擊城堡,若它攻擊城堡的時間為 $t$ 秒,那他會對城堡造成 $t$ 點傷害。每種魔法小奕都只能使用一次,同時為了避免魔力值不足,需要間隔 $A$ 秒才能再次發動魔法。綜合以上,小奕會在第 $A$ 秒、第 $2\times A$ 秒、第 $3\times A$ 秒、$\ldots$、第 $N\times A$ 秒發動魔法。另外,他的魔法功力不足以讓他控制施放的魔法種類,也因此每次他施放魔法時,他會施放其中一個還沒被他施放的魔法,且每一個的機率都是相同的。

小波在得知小奕要進攻後也進行了防範。他在城堡架設了一個砲台,砲台的攻擊速度為 $B$,代表在第 $B + 1$ 秒、第 $2\times B + 1$ 秒、第 $3\times B + 1$ 秒、$\ldots$ 時,若二維平面上有至少一個士兵,那它會瞄準目前離城堡圓心最近的一個士兵,並對他發射砲彈,若有多個距離最小的士兵會射向血量最小的一個,若再有多個血量最小的士兵那會射向任意一個。被砲彈擊中的士兵生命值會減少 1,當一個士兵生命值歸 0 後就會死亡,死亡的士兵會停止移動或攻擊。

現在告訴你所有的資訊,請計算小奕可以造成的傷害的期望值是多少。

Input Format

輸入第一行有六個整數 $x_c, y_c, r_c, A, B, N$。

接下來 $N$ 行,第 $i$ 行有三個整數 $x_i, y_i, h_i$,代表第 $i$ 個魔法的參數。

  • $1 \leq N \leq 8$
  • $-10^ 4 \leq x_c, y_c, x_i, y_i \leq 10^ 4$
  • $1 \leq r_c \leq 10^ 4$
  • $2 \leq A, B \leq 10^ 4$
  • $A, B$ 為偶數
  • $1 \leq h_i \leq 10$
  • $(x_c - x_i)^ 2 + (y_c - y_i)^ 2 > r_c^ 2$

Output Format

請輸出一行,該行有一個數代表小奕期望造成的傷害。若你的答案與正確答案的絕對誤差或相對誤差 $\leq 10^ {-6}$ 的話,則你的答案會被視為正確。

Sample Input 1

0 0 3 2 4 2
3 4 3
0 6 2

Sample Output 1

21

Sample Input 2

-5 -10 10 10 2 4
7 7 6
1 7 2
0 2 9
9 8 9

Sample Output 2

36.2026685331

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2