#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define pb push_back
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
const int MOD = 1000000000, N = 3000;
int delta[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool estVille[N][N], vue[N][N];
int dist[N][N];
int DistanceSum(int nVilles, int *X, int *Y) {
vector<pii> villes(nVilles);
int xMin = MOD, yMin = MOD;
for (int iVille = 0; iVille < nVilles; ++iVille){
villes[iVille] = {X[iVille], Y[iVille]};
chmin(xMin, X[iVille]);
chmin(yMin, Y[iVille]);
}
for (pii& ville : villes){
ville.x -= xMin;
ville.y -= yMin;
estVille[ville.x][ville.y] = true;
}
int sum = 0;
for (pii depart : villes){
for (pii ville : villes)
vue[ville.x][ville.y] = false;
queue<pii> file;
vue[depart.x][depart.y] = true;
dist[depart.x][depart.y] = 0;
file.push(depart);
while (!file.empty()){
pii noeud = file.front();
file.pop();
for (int i = 0; i < 4; ++i){
int ax = noeud.x + delta[i][0], ay = noeud.y + delta[i][1];
if (estVille[ax][ay] && !vue[ax][ay]){
vue[ax][ay] = true;
dist[ax][ay] = dist[noeud.x][noeud.y] + 1;
sum += dist[ax][ay];
file.push({ax, ay});
}
}
}
}
return sum/2;
}
