親愛的城市規劃師，感謝您接受我們的委託！
我們金石社區一共有$N$位居民，每位居民的住宅可視為平面上整數座標的一個點。為了提升社區福祉，我們打算興建一座公園，不過我們目前對公園的選址有所疑慮。
我們社區的道路如棋盤般方正整齊。為了讓居民行車前往公園時所花的時間最少，我們決定將這座公園設立在曼哈頓重心$C_M$的位置上：$C_M$就是與所有住宅之間的曼哈頓距離總和最小的位置。
更準確地說，若以$P_i$代表第$i$位居民的住宅位置，則$C_M$就是讓$\sum_i\text{ManhattanDistance}(C_M,P_i)$最小的位置。
然而，我們在進行規劃時發現了一個問題：我們社區中似乎混入了一名「不合群」的居民。他的住家位置格外偏遠，導致計算出來的曼哈頓重心偏離多數人的住所。我們認為，若能在計算曼哈頓重心時排除這位不合群的居民，那麼選出來的公園位置會更符合大眾要求。
不過，我們在辨認到底哪位居民不合群上遇到了困難，公園的進度也因此停擺。我們發布委託，正是期望您能協助我們找出這位不合群的居民。
（貼心附錄：對於兩點$(x_1,y_1)$與$(x_2,y_2)$，他們之間的曼哈頓距離為$|x_1-x_2|+|y_1-y_2|$。）
輸入第一行包含$N$。
接下來$N$行，每行都有兩個整數$x_i,y_i$，代表第$i$位居民的住宅位置。
- $2\le N\le 2\cdot10^5$
- $-10^9\le x_i,y_i\le 10^9$
Subtask:
- 30%: $N\le 1000$
- 70%: 無其他限制。
輸出一個數字$k$ $(0\leq k\leq N-1)$，代表將第$k$位居民排除在外後，剩餘的居民到新的曼哈頓中心$C_M'$的曼哈頓距離之和為最小。
即找出$k$讓$\sum_{i\ne k}\text{ManhattanDistance}(C_M',P_i)$為最小，其中$C_M'$為剩餘居民所形成的曼哈頓中心。
如果有多個符合條件的$k$，輸出最小的一個。
5 1 1 2 3 4 2 5 5 3 4
0
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.2s , <10M
公開 測資點#4 (10%): 1.2s , <10M
公開 測資點#5 (10%): 1.2s , <10M
公開 測資點#6 (10%): 1.2s , <10M
公開 測資點#7 (10%): 1.2s , <10M
公開 測資點#8 (10%): 1.2s , <10M
公開 測資點#9 (10%): 1.2s , <10M
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||