帶權中位數

P1（X1，Y1）、P2 （X2，Y2）、 P（Xp，

我國蒙古大草原上有 N（N 是不大於 100 的自然數）個牧民定居點 P1（X1，Y1）、P2
（X2，Y2）、 …Pn（Xn，Yn），相應地有關權重為 Wi，現在要求你在大草原上找一點 P（Xp，
Yp），使 P點到任 一點 Pi的距離 Di 與Wi 之積之和為最小。
即求 D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值
結論：對 x與 y兩個方向分別求解帶權中位數，轉化為一維。
設最佳點 p為點 k，則點 k 滿足：
令 W 為點 k到其餘各點的帶權距離之和，則
sigema( i=1 to k-1) Wi*Di = W/2
sigema( i=k+1 to n) Wi*Di = W/2
同時滿足上述兩式的點 k 即為帶權中位數。
{=============================華麗的分割線=========================================}
帶權中位數問題：
我們都學過中位數問題，即給定了N個數後，位於第N/2的數就是中位數。所謂帶權中位數，就是給定的N個數都有一個權值，或者說相當於個數。此時的中位數就不再是第N/2個數了，而是第∑DI/2個數。
而在信息學競賽中，有這樣一類題，給出了若干個排列在一條直線上的點，每個點有一個權值，比如說貨物量、人數什麼的，然後讓我們找出使所有點的貨物、人集合到一個點的總代價最小的位置。我們將會發現，這一類問題實際上就是帶權中位數問題。
{
一些符號的意思：
DI—第I個點的權值
DIST（I，J）—I到J點的距離，即DIST（I，J）=|NUMI-NUMJ|
由定義式易知：DIST（I，J）=DIST（J，I）
}
證明（簡）：
若最優點在T
則有：
∑{DI*DIST(I，T)}(IT)=∑{DI*DIST(I,T+1)}(IT+1)
將此式化為：
∑{DL}*DIST(L,T)}+∑{DR*DIST(R,T)}+DT+1*DIST(T+1,T)
=∑{DL}*DIST(L,T+1)}+∑{DR*DIST(R,T+1)}+DT*DIST(T,T+1) (LTRT+1)
即：
∑{DL*DIST(L,T+1)}-∑{DL*DIST(L,T)}(LT)+DT*(DIST(T,T+1))=∑{DR*DIST(R,T)}-∑(DR*DIST(R,T+1))(RT+1)+DT+1*(DIST(T,T+1))進一步化簡為：
∑{DL*(DIST(L,T)-DISTL,T+1)}(L=T)=∑{DR*(DIST(R,T+1)-DIST(R,T))}(R=T+1)∵DIST(L,T)-DIST(L,T+1)=DIST(T,T+1)
DIST(R,T+1)-DIST(R,T)=DIST(T+1,T)
OBVIOUSLY : DIST(T,T+1)=DIST(T+1,T)
因此：
∑DL(L=T)=∑(DR)(R=T+1)
即：∑DL(LT)+DT=∑(DR)(RT)
因此我們發現，若T是最優點，則必有其左邊的權值和加上DT後大於右邊的權值和
而類似的，我們可以證明其右邊的權值和加上DT後大於左邊的權值和
因此我們要找的點也就是滿足以上條件的點。注意到此時我們的選擇已經和具體的位置（坐標）沒有關係了，而成為主要考慮因素的僅僅是各點上的權值。
因為左邊的權值和數+DT=右邊的權值和，那么：
LEFTSUM+DT=RIGHTSUM=SUMALL-(LEFTSUM+DT)
=2*(LEFTSUM+DT)=SUMALL
=2*RIGHTSUM=SUMALL
同理可得：
RIGHTSUM+DT=LEFTSUM=SUMALL-(RIGHTSUM+DT)
=2*(RIGHTSUM+DT)=SUMALL
=2*LEFTSUM=SUMALL
此時我們發現：
2*LEFTSUM=SUMALL 而 2*(LEFTSUM+DT)=SUMALL
也即是說當前的位置T上的數包含了第(SUMALL)/2個數，由開篇的簡述可知，這第(SUMALL)/2個數，就是這個序列中的帶權中位數。所以這一類問題，實質上就是帶權中位數問題。
證明的簡單說明：
我們可以簡單地把上面的證明過程看作是左邊的人都集合到了M點，而右邊的人都集合到了M+1點。此時形成了兩軍對壘的形式，如果左邊的總人數比右邊的多，那么從左邊走到右邊去就沒有從右邊走到左邊來優，反之亦然。那么既然在當前點我們左邊的總人數已經比右邊多了，那么再往右邊移動，左邊的人數會進一步增多，而右邊的人會減少，那么只會導致更差的結果，所以此時我們可以判斷最優點一定在當前點的左邊，或者至少在當前這個點。那么範圍就從當前的L，R縮小到了L，M，通過不斷地縮小範圍（而每一次縮小我們都砍掉了一半的範圍），最後我們得到的將是一個點——那就是我們要求的集合位置。
NOTIFY THAT THE CHOICE OF THE MEETPLACE HAS NOTHING TO DO WITH THE DISTANCES！！
最優位置的選擇與距離無關！！
-------------------------By GODRIC