สามารถสรุปใจความโจทย์ได้ว่า กำหนดจุดทั้งหมด $N$ จุด โดยจุดที่ $i$ อยู่ที่พิกัด $(X_i, Y_i)$ จงหา $\sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \left( |X_i-X_j| + |Y_i-Y_j| \right)$

สังเกตว่าเราสามารถแยกคิดผลบวกในแกน X และแกน Y ได้ นั่นคือ เราต้องการหา

$\left( \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} |X_i-X_j| \right) + \left( \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} |Y_i-Y_j| \right)$

หากเราต้องการหาผลรวมของระยะห่างระหว่างจุดทุกคู่โดยสนใจเพียงแกนเดียว การคำนวณทุกคู่จุดตรง ๆ จะต้องใช้เวลาถึง $O(N^2)$ ซึ่งไม่ทันสำหรับกรณีที่ $N$ มีค่ามากถึง $500\,000$

เราสามารถลดระยะเวลาการทำงานได้โดยการเรียงลำดับพิกัดแต่ละแกนจากน้อยไปมาก จะเห็นว่า ระยะทางแต่ละคู่จุดสามารถแยกออกเป็นส่วน ๆ ได้

ยกตัวอย่าง หากพิกัดแกน X เป็น $2, 3, 5, 7, 11$ จะมีคู่จุดที่นำมาแบ่งส่วนระยะทางได้ดังนี้

• $|2-3|$
• $|2-5|$ แยกเป็น $|2-3|+|3-5|$
• $|2-7|$ แยกเป็น $|2-3|+|3-5|+|5-7|$
• $|2-11|$ แยกเป็น $|2-3|+|3-5|+|5-7|+|7-11|$
• $|3-5|$
• $|3-7|$ แยกเป็น $|3-5|+|5-7|$
• $|3-11|$ แยกเป็น $|3-5|+|5-7|+|7-11|$
• $|5-7|$
• $|5-11|$ แยกเป็น $|5-7|+|5-11|$
• $|7-11|$

ดังนั้น ผลรวมของระยะห่างแต่ละคู่ คิดได้จากการรวมระยะทาง

• $|2-3|$ ทั้งหมด $4$ ครั้ง
• $|3-5|$ ทั้งหมด $6$ ครั้ง
• $|5-7|$ ทั้งหมด $6$ ครั้ง
• $|7-11|$ ทั้งหมด $4$ ครั้ง

เข้าด้วยกัน ได้คำตอบของแกน X เป็น $4|2-3| + 6|3-5| + 6|5-7| + 4|7-11| = 44$

กล่าวโดยทั่วไป ระยะห่างระหว่างจุดที่ $i$ กับ $i+1$ ($1 \leq i < N$) จะต้องนำมาคิดทั้งหมด $i \cdot (N-i)$ ครั้ง เพราะว่าระยะช่วงนั้นจะถูกคิดจากการจับคู่จุดที่อยู่ทางด้านซ้ายทั้งหมด $i$ จุดกับจุดที่อยู่ทางด้านขวา $N-i$ จุดเข้าด้วยกันได้ $i \cdot (N-i)$ คู่

Implementation

ในภาษา C:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef long long ll;

int n;
int x[500000];
int y[500000];

int cmpfunc(const void *a, const void *b) { return (*(int *)a - *(int *)b); }

int main(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d %d", &x[i], &y[i]);

  ll dist = 0;

  qsort(x, n, sizeof(int), &cmpfunc);
  qsort(y, n, sizeof(int), &cmpfunc);
  ll sumx = 0;
  ll sumy = 0;
  for (int i = 1; i < n; i++) {
    int diffx = (x[i] - x[i - 1]);
    sumx += diffx * i;
    int diffy = (y[i] - y[i - 1]);
    sumy += diffy * i;

    dist += sumx + sumy;
  }

  printf("%lld", dist);
  return 0;
}