STEP5::Problem 0056 : Ch特別篇-10.距離

有點數學的題目。
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0056
題目給你N個點，問這N個點距離的平方和，也就是每個點會有N(N-1)/2條邊，這些邊的平方和。

首先，這題先拆成X和Y軸，最後加起來就可以。再來用類似求區間和的感覺，只是要轉換一下。先照座標排序，O(n)跑出座標差和前綴和，順便紀錄前綴和的平方的總和，做完後這個總和就是第一個點到所有點距離的平方和，再來推到第二個點，用和的平方公式，他們的到所有點的距離的平方和(去掉跟第一個點的)就是本的總和扣掉 點1到點2 距離的平方(a平方)在去掉2*這段長度*後面的長度(2ab)，剩下的就是後面點的平方和(b平方)，用分配律換一下就可以O(n)求解。