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

內容

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

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

$x = (x_1, \cdots, x_n)$ 和 $y = (y_1, \cdots, y_n)$ 之間的距離為

$$d(x, y) := \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + \cdots + (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 (碼畜) ]

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