b348. 最近餐館 - 高中生程式解題系統

內容

每到吃飼料時間，某 M 正思考要去哪裡解決，雖然有很多很多地方可以去吃，由於某 M 對於美食沒有特別需求，所以只會到最近的 $P$ 個地點即可，然後再以循環輪食的方式日復一日。

當前位置與每個餐館的位置都用一個笛卡爾坐標系中的點表示，每個點之間的距離為歐幾里得距離。

$x = (x_{1}, \dots, x_{n})$ 和 $y = (y_{1}, \dots, y_{n})$ 之間的距離為

$d (x, y) := \sqrt{(x_{1} - y_{1})^{2} + (x_{2} - y_{2})^{2} + \dots + (x_{n} - y_{n})^{2}} = \sqrt{\sum_{i = 1}^{n} (x_{i} - y_{i})^{2}}$

現給出在

K

維空間中某 M 所處的位置座標，以及

N

個餐館位置，請觀察某 M 會到哪裡吃飼料。.

輸入說明

輸入有多組測資，

每一組第一行會有兩個整數 $N, K$ ，

接下來會有 $N$ 行，每行包含 $K$ 個整數，表示第 $i$ 個餐館座標。

接下來一行，包含一個整數 $Q$ ，表示某 M 的可能座標數量。

接下來會有 $Q$ 行，每一組詢問會有兩行，第一行會有 $K$ 個整數，表示某 M 所在的座標，第二行會有一個整數 $P$ 。

輸出說明

對於每一組詢問，輸出一行 `Case #: `，第一個整數為

P

，接下來

P

個整數按照距離由小到大輸出餐館編號，如果相同則輸出編號小的。

範例輸入 #1

範例輸出 #1

Case 1: 1 1
Case 2: 2 2 3
Case 3: 1 2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (50%): 2.0s , <1M
公開測資點#1 (20%): 2.0s , <10M
公開測資點#2 (20%): 2.0s , <10M
公開測資點#3 (5%): 2.0s , <10M
公開測資點#4 (5%): 2.0s , <10M

提示：

有任何時限問題，歡迎來信告知。希望能讓各種特殊算法通過此題。

標籤:

KD樹搜索結構計算幾何

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」