#include <bits/stdc++.h> using namespace std; typedef long long ll; map<pair<int,int>, bool> exists; map<pair<int,int>, int> node_of; int sz[100000]; int sub_sz[100000] = {0}; bool vis[100000]; int dfs(pair<int,int> u) { vis[node_of[u]] = true; int cur_x = u.first; sub_sz[node_of[u]] = sz[node_of[u]]; while (exists[{++cur_x, u.second}] == true) { if (exists[{cur_x, u.second - 1}] == true && !vis[node_of[{cur_x, u.second - 1}]]) sub_sz[node_of[u]] += dfs({cur_x, u.second - 1}); if (exists[{cur_x, u.second + 1}] == true && !vis[node_of[{cur_x, u.second + 1}]]) sub_sz[node_of[u]] += dfs({cur_x, u.second + 1}); } cur_x = u.first + 1; while (exists[{--cur_x, u.second}] == true) { if (exists[{cur_x, u.second - 1}] == true && !vis[node_of[{cur_x, u.second - 1}]]) sub_sz[node_of[u]] += dfs({cur_x, u.second - 1}); if (exists[{cur_x, u.second + 1}] == true && !vis[node_of[{cur_x, u.second + 1}]]) sub_sz[node_of[u]] += dfs({cur_x, u.second + 1}); } return sub_sz[node_of[u]]; } int solve(int N, int *X, int *Y) { exists.clear(); node_of.clear(); for (int i = 0; i < N; i++) exists[{X[i], Y[i]}] = true; int node = -1; for (int i = 0; i < N; i++) { if (node_of[{X[i], Y[i]}] != 0) continue; node_of[{X[i], Y[i]}] = ++node; int cur_x = X[i]; while (exists[{--cur_x, Y[i]}] == true) node_of[{cur_x, Y[i]}] = node; cur_x = X[i]; while (exists[{++cur_x, Y[i]}] == true) node_of[{cur_x, Y[i]}] = node; } fill_n(sz, 0, node + 1); fill_n(sub_sz, 0, node + 1); fill_n(vis, false, node + 1); for (int i = 0; i < N; i++) sz[node_of[{X[i], Y[i]}]]++; dfs({X[0], Y[0]}); ll res = 0; for (int i = 1; i < node; i++) res += sub_sz[i] * (N - sub_sz[i]), res %= 1'000'000'000; return res; } int DistanceSum(int N, int *X, int *Y) { return (solve(N, X, Y) + solve(N, Y, X)) % 1'000'000'000; } /* int nn; int xx[100000], yy[100000]; int main() { ifstream cin("example.txt"); //ofstream cout("output.txt"); cin >> nn; for (int i = 0; i < nn; i++) cin >> xx[i] >> yy[i]; cout << DistanceSum(nn, xx, yy) << '\n'; return 0; } */