題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing
房屋仲介小潮負責高談市的租房業務。小潮手上有編號為 $1, 2, · · · , n$ 的 $n$ 間待租的房屋，房屋 $i$ 的位置可以用二維座標 $(a_i, b_i)$ 表示，並且此房屋的月租金為 $r_i$ 元。
高談市有 $m$ 座捷運站，捷運站的編號為 $1, 2, · · · , 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 ≤ n ≤ 10^5$。
• $1 ≤ m ≤ 10^3$。
• $−10^9 ≤ a_i, b_i, c_i, d_i ≤ 10^9$。
• $0 ≤ r_i ≤ 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$ 名的房屋編號。
3 3 2 0 11000 5 0 12000 3 3 10000 1 3 3 0 5 3
1 3 2
4 2 2 -2 10000 -2 1 12000 1 -3 12000 4 5 19000 1 5 4 1
4 1 2 3
公開 測資點#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 ≤ 2$ | #02~#07 |
| 2 | 30 | $n ≤ 100$ | #08~#10 |
| 3 | 50 | 無額外限制 | #11~#13 |
如果題目有問題歡迎來信詢問！
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 39495 | P2006950413 (說不得) | k184 | 66 | 2024-02-28 17:38 |