k184. pA. 房屋推薦 (house) - 高中生程式解題系統

內容

題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

房屋仲介小潮負責高談市的租房業務。小潮手上有編號為 $1, 2, \cdot \cdot \cdot, n$ 的 $n$ 間待租的房屋，房屋 $i$ 的位置可以用二維座標 $(a_{i}, b_{i})$ 表示，並且此房屋的月租金為 $r_{i}$ 元。

高談市有 $m$ 座捷運站，捷運站的編號為 $1, 2, \cdot \cdot \cdot, m$ ，捷運站 $j$ 的位置在二維平面以座標 $(c_{j}, d_{j})$ 表示。定義房屋 $i$ 與捷運站 $j$ 的距離為 $\sqrt{(a_{i} - c_{j})^{2} + (b_{i} - d_{j})^{2}}$ 單位。

小潮發現租客的喜好如下：

1. 房屋與最近的捷運站的距離越短越好。
2. 如果兩間房屋和彼此最近的捷運站距離一樣近，月租金越小的房屋越好。
3. 如果兩間房屋和彼此最近的捷運站距離一樣近，而且月租金相同，房屋編號越小的越好。

請幫忙小潮開發一個房屋推薦系統，對房屋們進行排序，使得越是得到租客喜愛的房屋排在越前面。

如下圖為一 $n = 3$ 且 $m = 3$ 的例子，其中正方形的點 $H_{1}, H_{2}, H_{3}$ 分別代表房屋 $1, 2, 3$ ，圓點 $S_{1}, S_{2}, S_{3}$ 則分別代表捷運站 $1, 2, 3$ 的位置。並且：

• 第 $1$ 間房屋位在 $(2, 0)$ ，月租金為 $11000$ 元。
• 第 $2$ 間房屋位在 $(5, 0)$ ，月租金為 $12000$ 元。
• 第 $3$ 間房屋位在 $(3, 3)$ ，月租金為 $10000$ 元。
• 第 $1$ 座捷運站位在 $(1, 3)$ 。
• 第 $2$ 座捷運站位在 $(3, 0)$ 。
• 第 $3$ 座捷運站位在 $(5, 3)$ 。

測資限制

• $1 \leq n \leq 10^{5}$ 。
• $1 \leq m \leq 10^{3}$ 。
• $- 10^{9} \leq a_{i}, b_{i}, c_{i}, d_{i} \leq 10^{9}$ 。
• $0 \leq r_{i} \leq 10^{9}$
• 上述變數皆為整數。
• 任意一個座標最多只有一間房屋或一座捷運站，且不會有房屋和捷運站在同一座標。

輸入說明

n

m

a_{1}

b_{1}

r_{1}

a_{2}

b_{2}

r_{2}

...

a_{n}

b_{n}

r_{n}

c_{1}

d_{1}

c_{2}

d_{2}

...

c_{m}

d_{m}

• $n, m$ 分別代表房屋與捷運站的數量。
• 房屋 $i$ 的座標在 $(a_{i}, b_{i})$ ，且租金為 $r_{i}$ 。
• 捷運站 $j$ 的座標為 $(c_{j}, d_{j})$ 。

輸出說明

p_{1}

p_{2}

...

p_{n}

• $p_{i}$ 為一整數，代表排名第 $i$ 名的房屋編號。

範例輸入 #1

範例輸出 #1

1
3
2

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (1%): 1.0s , <1K
公開測資點#1 (1%): 1.0s , <1K
公開測資點#2 (3%): 1.0s , <1M
公開測資點#3 (3%): 1.0s , <1M
公開測資點#4 (3%): 1.0s , <1M
公開測資點#5 (3%): 1.0s , <1M
公開測資點#6 (3%): 1.0s , <1M
公開測資點#7 (3%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <1M
公開測資點#10 (10%): 1.0s , <1M
公開測資點#11 (16%): 1.0s , <10M
公開測資點#12 (17%): 1.0s , <10M
公開測資點#13 (17%): 1.0s , <10M

提示：

題目和測資來源 : twpca

注意因為礙於系統問題測試資料沒辦法完整的放上來（其實這題有全放啦）。

子任務	分數	額外輸入限制	測資點
1	20	$n \leq 2$	#02~#07
2	30	$n \leq 100$	#08~#10
3	50	無額外限制	#11~#13

如果題目有問題歡迎來信詢問！

標籤:

排序

出處:

TOI入營考 2023 [管理者： Ststone1687 (Ststone) ]

編號	身分	題目	主題	人氣	發表日期
39495	P2006950413 (說不得)	k184	11%的問題	292	2024-02-28 17:38