[HOJ 277][GCJ 2013 1B]Falling Diamonds (題目備份)

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/277_files/extensions/MathMenu.js

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 277 - Falling Diamonds

Special Judge

Problem Statistics

Solved Member: 10　　Submission: 66　　User Tried: 11

Problem：

有很多方形的鑽石從天上掉了下來，現在貪心的Zeko想要去撿鑽石。

但是Zeko是懶惰的，所以在他確認一個位置有沒有鑽石之前，他不會去撿鑽石。

我們說一個位置有鑽石，代表有一個鑽石的「中心點」落在該座標上，我們保證所有鑽石的中心點座標都是格子點。

每個鑽石除了自己的座標(x , y)之外，它的頂點還會碰到(x-1 , y),(x+1 , y),(x , y-1),(x , y+1)四個座標。

現在有無數顆鑽石從(0 , ∞)垂直掉下來，∞是一個非常大的座標，這些鑽石會不斷落下直到它們打到地面(y = 0)或是卡在兩顆鑽石中間。

當鑽石打到地面，它就會埋入地面直到中心點在 y = 0 。
如果鑽石是邊碰邊和另一個鑽石相撞，它就會沿著鑽石邊形成的斜面滑下(即移動的路徑的斜率為 1 或者 -1)。
如果鑽石是頂點碰頂點和另一個鑽石相撞，它滑向左邊或滑向右邊的機率會是相等的。

如下圖，有可能為其中一種鑽石掉下來的情況

注意到，第二顆鑽石的中心座標為 (-2, 0)，但是他也有機會掉在座標 (2, 0) 的位置，並影響到其他的鑽石掉在其他地方的機率。

現在告訴你總共有多少個鑽石從(0, ∞)落下，並且給你Zeko想要關心的座標(X, Y)。請輸出任何一個鑽石落在該座標的機率。

Input：

輸入的第一行是一個整數T(1 ≤ T ≤ 100)，代表接下來有幾筆測試資料。
每筆測試資料佔一行，包含三個數字N(1 ≤ N ≤ 1000000), X (-10,000 ≤ X ≤ 10,000), Y (0 ≤ Y ≤ 10,000)，分別代表總共有N個鑽石落下、Zeko關心的座標(X, Y)。

Output：

對於每一筆測試資料，請輸出一行，包含一個數字，代表Zeko關心的座標存在一顆鑽石的機率。你輸出的答案與我們的解答必須差在 10^-6 以內。

Sample Input：

7
1 0 0
1 0 2
3 0 0
3 2 0
3 1 1
4 1 1
4 0 2

Sample Output：

1.0
0.0
1.0
0.75
0.25
0.5
0.0

Source：

Google Code Jam 2013 1B

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0	10000ms	262144kb
1	10000ms	262144kb	10
2	10000ms	262144kb	10
3	10000ms	262144kb	10
4	10000ms	262144kb	70

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。