帶權中位數定義如下:

郵局位置問題定義如下:

上一篇文章輸油管道問題里面證明了,當權值Wi都為1的時候,中位數就是最佳的解。但是,現在Wi已經不一定是1了。所以,現在
需要證明在任意Wi的取值情況下,帶權中位數能夠成為郵局位置的最佳解。假設,所有Wi都是1的倍數,如果是小數的話,可以所有的
Wi都乘以一定的倍數。那么wi*d(p,pi) =
Σ(p,pi)(i從1到wi),這個意思是把距離乘以了wi倍。
但是,現在可以換一種看法,換成了pi位置有wi個重合的點,且每一個點的權值都是1,那么其和也是wi*d(p,pi)。那么對所有的pi
都這樣分解,就把問題重新轉換成了輸油管道問題了。輸油管道問題的最優解就是中位數,那么郵局問題的最優解就是轉換之后的
這些點的中位數點。而這個點一定存在于帶權中位數那個點分解出的一堆點中。
二維郵局問題的解法是把x和y分開求2次一維郵局問題,然后把解組和起來,得到答案。
求帶權中位數的算法比較簡單,直接的做法是,先把n個點按照位置排序,然后按點的位置從小到大遍歷,找到滿足要求的點即可。
不算排序點位置的預處理,因為很多時候點應該就是按順序給出的,所以其時間復雜度是O(n)。
要求: