#include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; const ll MOD = 1e9; int N; pair<int, int> sorted[2][100001]; set<int> graphs[2][100001]; ll num_blocks[2][100001], dp[2][100001], ans = 0; int x = 0, y = 0; map<pair<int, int>, int> x_cmp, y_cmp; void dfs1(int dir, int node, int parent = 0) { for (int i : graphs[dir][node]) if (i != parent) { dfs1(dir, i, node); dp[dir][node] += dp[dir][i]; ans = (ans + (N - dp[dir][i]) * dp[dir][i]) % MOD; } } int DistanceSum(int N, int *X, int *Y) { ::N = N; FOR(i, 0, N) { sorted[0][i] = {X[i], Y[i]}; sorted[1][i] = {Y[i], X[i]}; } sort(sorted[0], sorted[0] + N); sort(sorted[1], sorted[1] + N); FOR(i, 0, N) { if (i == 0 || sorted[0][i].second - sorted[0][i - 1].second != 1 || sorted[0][i].first != sorted[0][i - 1].first) { y++; } dp[0][y]++; y_cmp[sorted[0][i]] = y; if (y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]) { graphs[0][y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]].insert(y); graphs[0][y].insert(y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]); } } FOR(i, 0, N) { if (i == 0 || sorted[1][i].second - sorted[1][i - 1].second != 1 || sorted[1][i].first != sorted[1][i - 1].first) { x++; } dp[1][x]++; x_cmp[sorted[1][i]] = x; if (x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]) { graphs[1][x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]].insert(x); graphs[1][x].insert(x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]); } } dfs1(0, 1); dfs1(1, 1); return (int)ans; }