a580: 輻射擴散
Tags :
Accepted rate : 22人/37人 ( 59% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-25 00:10

Content
Background


出國比 ACM-ICPC 區預賽,沒有好英文可是不行的。小光這次去泰國合艾打醬油,題目根本看不懂,猶如同 WORLD FINAL 的選手不會應答現場主播,被大陸觀眾講「這傢伙不會英文怎麼做題的?」當然小光沒那麼厲害,不過一只蟲子罷了,誰也沒放在眼裡。

根據小光解析題目,泰國合艾 Problem D Radiation 在描述兩個核子輻射的影響範圍,每在一個輻射影響範圍內則會獲得一個保護裝置,因此在交集處的房子可以獲得兩個保護裝置。而多的那一份可以交給沒有保護裝置的房子以防萬一輻射擴散。原題求給定分別兩個的輻射半徑,問有多少房子沒有辦法拿到保護裝置。

當下小光並不是這麼想的,誤以為是要求交集處的房子有多少個。

The Problem

給定平面上 N 個房子的點座標,以及兩個輻射源的點座標。對於 Q 個詢問,每個詢問給定第一與第二輻射源的半徑,求交集處的房子個數(剛好在圓上也是在輻射範圍內)。

Input

多筆測資。

每組第一行有一個整數 N,

接下來有 N 行平面的房子整數座標 (x, y),

以及在 N+2 行給定兩個輻射源 (ax, ay) (bx, by) 以及一個整數 Q 詢問,

接下來有 Q 行詢問 (r1, r2),r1 是 (ax, ay) 的半徑,r2 是 (bx, by) 的半徑

所有數據數值小於等於 20000 的非負整數。

N = 0 時結束。

Output
對每組輸出交集處的點個數,請參照範例輸出。
Sample Input #1
11
95 75
27 6
93 5
124 13
34 49
65 61
81 49
77 33
110 50
91 22
110 25
57 42 97 36 2
31 25
25 25
0
Sample Output #1
Case 1:
2
2
 
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :
Tags:
出處:
ACM-ICPC Hatyai 改編 [管理者:
morris1028 (碼畜)
]


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