b358: 竹馬不敵天降
Tags : Voronoi Diagram 半平面交 計算幾何
Accepted rate : 4人/12人 ( 33% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-06-15 06:27

Content

「話說,剛剛明明說的是合乎聖誕節的商品。這不是 H-GAME 嗎?哪裡有聖誕元素啊!」
「嗯,真虧你發現這點啊,但還是有點可惜,這是全齡版,沒有工口哦!」
「不管怎麼樣,一點也沒合聖誕節啊。」
「雖然你有好好學習許多東西,但對本質上完全沒有理解。」
「最近開始覺得有點明白了 …」
「那麼就來說明下這個作品吧」
「是一年前發售的大人氣美少女遊戲的續篇吧?」
「是的,那為什麼你沒有察覺到-『一年前』這句話所包含的意義」
「對於期盼著的人那就意味著 … 與戀人時隔一年的再會!」

在 GALGAME 故事發展過程中,竹馬幾乎沒勝過天降,走哪一條故事線進行發展正是玩 GALGAME 的樂趣。

然而有一款極為糟糕的 GALGAME 的初始方式則是在一開始選定座標下,系統會根據座標找到附近最鄰近少女,並且在隨後的故事情節都會圍繞這名少女。

遊戲的地圖設計很簡單,用一個矩形表示,現在已知 N 名少女的所在地 (都在矩形內部)。一開始選定的座標也必須落在矩形內,請問玩每個故事線機率分布為何?

Input

輸入有多組測資。

每組第一行會有三個整數 N, A, B,表示在 [0 : A] x [0 : B] 地圖中有 N 個已知座標。
接下來會有 N 行,第 i 行上會有兩個整數 x, y,表示第 i 位少女所在的座標 (x, y) 保證不會有重疊的情況。

(0 < N <= 100, 0 < A, B <= 1000, 0 <= x <= A, 0 <= y <= B)

Output
對於每組測資輸出一行,輸出故事線機率高低,優先輸出機率高的故事線編號,機率相同時,按照輸入順序輸出編號。
Sample Input
2 5 3
1 2
4 2

2 5 3
1 1
2 2

3 5 3
1 1
2 2
4 1
Sample Output
Case 1: 1 2
Case 2: 2 1
Case 3: 3 2 1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 6.0s , <1K
公開 測資點#1 (30%): 10.0s , <1M
公開 測資點#2 (20%): 10.0s , <1M
Hint :

怕浮點數誤差,將機率輸出修正為按照大小輸出。

距離計算為歐幾里得距離,以下為故事線編號對應的機率。

Case 1:
1 0.500000
2 0.500000

Case 2:
2 0.700000
1 0.300000

Case 3:
3 0.395833
2 0.312500
1 0.291667

機率計算方式: 故事線 i 可以觸發的面積 / 總面積

 

#define eps 1e-6  對於機率 p 的比較,在 fabs(x.p - y.p) <= eps 視為相同。

 

Tags:
Voronoi Diagram 半平面交 計算幾何
出處:
妮可 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」