#include <iostream> #include <vector> #include <algorithm> #include <set> #include <queue> #include <map> using namespace std; int N; vector<int> X, Y; const int MX = 100'000; const int INF = 1'000'000'000; struct point { int x; int y; int i; int rightNodes; int downNodes; }; bool operator < (point A, point B) { if(A.x != B.x) return A.x < B.x; return A.y < B.y; } set<point> P; int getIndex(int x, int y) { set<point>::iterator f = P.find(point{x, y, -1, -1, -1}); if(f == P.end()) return -1; else return f->i; } vector<int> up_edge[1+MX]; vector<int> down_edge[1+MX]; vector<int> Y_index_size(1+MX); vector<int> Y_index_coord(1+MX); int Y_max_index; vector<int> Y_parent(1+MX); vector<int> Y_subtree_sum(1+MX); vector<int> down_reach(1+MX); vector<int> point_Y_line(1+MX); void Y_dfs(int u, int p) { // cerr << "Y dfs " << u << ' ' << p << '\n'; Y_subtree_sum[u] = Y_index_size[u]; for(int v: up_edge[u]) { if(v == p) continue; Y_parent[v] = u; Y_dfs(v, u); Y_subtree_sum[u] += Y_subtree_sum[v]; } for(int v: down_edge[u]) { if(v == p) continue; Y_parent[v] = u; Y_dfs(v, u); Y_subtree_sum[u] += Y_subtree_sum[v]; } } vector<int> left_edge[1+MX]; vector<int> right_edge[1+MX]; vector<int> X_index_size(1+MX); vector<int> X_index_coord(1+MX); int X_max_index; vector<int> X_parent(1+MX); vector<int> X_subtree_sum(1+MX); vector<int> right_reach(1+MX); vector<int> point_X_line(1+MX); void X_dfs(int u, int p) { X_subtree_sum[u] = X_index_size[u]; for(int v: left_edge[u]) { if(v == p) continue; X_parent[v] = u; X_dfs(v, u); X_subtree_sum[u] += X_subtree_sum[v]; } for(int v: right_edge[u]) { if(v == p) continue; X_parent[v] = u; X_dfs(v, u); X_subtree_sum[u] += X_subtree_sum[v]; } } long long init_dist = 0; vector<int> dx{0, 0, +1, -1}; vector<int> dy{+1, -1, 0, 0}; long long final_ans = 0; vector<bool> visit(MX, 0); map<pair<int, int>, long long> X_delta, Y_delta; //adjust value when going from u to v. void dfs(int u) { for(int z = 0; z < 4; z++) { int v = getIndex(X[u] + dx[z], Y[u] + dy[z]); if(v == -1) continue; if(visit[v]) continue; visit[v] = 1; long long adjust_val; // if(Y[v] < Y[u]) // { // adjust_val = N - (right_reach[ point_X_line[v] ] - X_index_size[ point_X_line[v] ]); // } // else if(Y[u] < Y[v]) // { // // cerr << "moving right\n"; // adjust_val = right_reach[ point_X_line[u] ] - X_index_size[ point_X_line[u] ]; // // cerr << "adjust_val = " << adjust_val << '\n'; // // cerr << right_reach[ point_X_line[u] ] << '\n'; // } // else if(X[v] < X[u]) // { // adjust_val = N - (down_reach[ point_Y_line[v] ] - Y_index_size[ point_Y_line[v] ]); // } // else // { // adjust_val = down_reach[ point_Y_line[u] ] - Y_index_size[ point_Y_line[u] ]; // } // adjust_val = delta[ make_pair(u, v) ]; if(X[u] == X[v]) { adjust_val = X_delta[ make_pair(point_X_line[u], point_X_line[v]) ]; } else { // cerr << "! \n"; // cerr << point_Y_line[u] << ' ' << point_Y_line[v] << ' ' << Y_delta[ make_pair(point_Y_line[u], point_Y_line[v]) ] <<'\n'; adjust_val = Y_delta[ make_pair(point_Y_line[u], point_Y_line[v]) ]; } init_dist += (N - adjust_val) - adjust_val; final_ans += init_dist; // cerr << v << " -> " << init_dist << '\n'; dfs(v); init_dist -= (N - adjust_val) - adjust_val; } } int DistanceSum(int N_, int *X_, int *Y_) { //PART 1: Normalize // cerr << "check\n"; N = N_; X = vector<int>(N); Y = vector<int>(N); for(int i = 0; i < N; i++) { X[i] = X_[i]; Y[i] = Y_[i]; } int Xmin = X[0], Ymin = Y[0]; for(int i = 1; i < N; i++) { Xmin = min(Xmin, X[i]); Ymin = min(Ymin, Y[i]); } // cerr << "\n\n\n\n\n\n"; for(int i = 0; i < N; i++) { X[i] = X[i] - Xmin + 1; Y[i] = Y[i] - Ymin + 1; //CORRECT THIS!!!!!! // cerr << X[i] << ' ' << Y[i] << '\n'; } for(int i = 0; i < N; i++) { P.insert(point{X[i], Y[i], i, -1, -1}); } //PART 2: Find the vertical strips. vector<int> Ylist[1+MX]; for(int i = 0; i < N; i++) { Ylist[ X[i] ].push_back(Y[i]); } for(int x = 1; x <= MX; x++) sort(Ylist[x].begin(), Ylist[x].end()); // // int curr_Y_index = 0; vector<int> Y_begin[1+MX], Y_end[1+MX]; vector<int>* Y_index = new vector<int>[1+MX]; //FIGURE OUT WHY THIS WENT WRONG // vector<int> Y_index[1+MX]; for(int x = 1; x <= MX; x++) { if(Ylist[x].empty()) continue; Y_begin[x].push_back(Ylist[x][0]); curr_Y_index++; Y_index[x].push_back(curr_Y_index); for(int i = 1; i < (int)Ylist[x].size(); i++) { if(Ylist[x][i-1] + 1 != Ylist[x][i]) { Y_end[x].push_back(Ylist[x][i-1]); Y_begin[x].push_back(Ylist[x][i]); curr_Y_index++; Y_index[x].push_back(curr_Y_index); } } Y_end[x].push_back(Ylist[x].back()); // cerr << "x = " << x << '\n'; for(int v = 0; v < (int)Y_begin[x].size(); v++) { // cerr << Y_begin[x][v] << ' ' << Y_end[x][v] << ' ' << Y_index[x][v] << '\n'; Y_index_size[ Y_index[x][v] ] = Y_end[x][v] - Y_begin[x][v] + 1; Y_index_coord[ Y_index[x][v] ] = x; for(int y = Y_begin[x][v]; y <= Y_end[x][v]; y++) point_Y_line[ getIndex(x, y) ] = Y_index[x][v]; } } for(int x = 1; x+1 <= MX; x++) { if(Y_index[x].empty() || Y_index[x+1].empty()) continue; int q = 0; for(int p = 0; p < (int)Y_index[x].size(); p++) { if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q])) { down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]); up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]); } while(q+1 < (int)Y_begin[x+1].size() && Y_begin[x+1][q+1] <= Y_end[x][p]) { q++; if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q])) { down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]); up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]); } } } } Y_max_index = curr_Y_index; Y_parent[1] = 0; Y_dfs(1, 1); for(int u = 1; u <= Y_max_index; u++) { down_reach[u] = Y_index_size[u]; for(int v: down_edge[u]) { if(v == Y_parent[u]) { down_reach[u] += N - Y_subtree_sum[u]; Y_delta[ make_pair(u, v) ] = (N - Y_subtree_sum[u]); Y_delta[ make_pair(v, u) ] = Y_subtree_sum[u]; // cerr << "delta " << u << ' ' << v << " ;; " << Y_delta[make_pair(u, v)] << '\n'; } else { down_reach[u] += Y_subtree_sum[v]; Y_delta[ make_pair(u, v) ] = Y_subtree_sum[v]; Y_delta[ make_pair(v, u) ] = (N - Y_subtree_sum[v]); // cerr << "delta " << u << ' ' << v << " ;; " << Y_delta[make_pair(u, v)] << '\n'; } } // cerr << u << ' ' << Y_index_coord[u] << ' ' << Y_index_size[u] << " : " << down_reach[u] << '\n'; } // for(int i = 0; i < N; i++) cerr << X[i] << ' ' << Y[i] << ' ' << down_reach[ point_Y_line[i] ] << '\n'; // cerr << "\n\n\n\n checking horizontal\n\n\n"; //PART 3: Find the horizontal strips vector<int>* Xlist = new vector<int>[1+MX]; for(int i = 0; i < N; i++) { Xlist[ Y[i] ].push_back(X[i]); } for(int y = 1; y <= MX; y++) sort(Xlist[y].begin(), Xlist[y].end()); int curr_X_index = 0; vector<int>* X_begin = new vector<int>[1+MX]; vector<int>* X_end = new vector<int>[1+MX]; vector<int>* X_index = new vector<int>[1+MX]; //FIGURE OUT WHY THIS WENT WRONG // vector<int> X_index[1+MX]; // cerr << "check5\n"; for(int y = 1; y <= MX; y++) { // if(y <= 10) cerr << "y = " << y << '\n'; if(Xlist[y].empty()) continue; X_begin[y].push_back(Xlist[y][0]); curr_X_index++; X_index[y].push_back(curr_X_index); for(int i = 1; i < (int)Xlist[y].size(); i++) { if(Xlist[y][i-1] + 1 != Xlist[y][i]) { X_end[y].push_back(Xlist[y][i-1]); X_begin[y].push_back(Xlist[y][i]); curr_X_index++; X_index[y].push_back(curr_X_index); } } X_end[y].push_back(Xlist[y].back()); // cerr << "y = " << y << '\n'; for(int v = 0; v < (int)X_begin[y].size(); v++) { // cerr << "v = " << v << '\n'; // cerr << X_begin[y][v] << ' ' << X_end[y][v] << ' ' << X_index[y][v] << '\n'; X_index_size[ X_index[y][v] ] = X_end[y][v] - X_begin[y][v] + 1; X_index_coord[ X_index[y][v] ] = y; // cerr << "y = " << y << ", x1 = " << X_begin[y][v] << ", x2 = " << X_end[y][v] << '\n'; for(int x = X_begin[y][v]; x <= X_end[y][v]; x++) { // cerr << " x = " << x << '\n'; // cerr << int(P.find(point{x, y, -1, -1, -1}) == P.end()) << '\n'; // cerr << getIndex(x, y) << ' ' << X_index[y][v] << '\n'; point_X_line[ getIndex(x, y) ] = X_index[y][v]; // cerr << " ended\n"; } // cerr << "ended\n"; } } // cerr << "\n\n"; // for(int i = 0; i < N; i++) cerr << i << ' ' << X[i] << ' ' << Y[i] << " > " << point_X_line[i] << '\n'; // cerr << "check6\n"; for(int y = 1; y+1 <= MX; y++) { if(X_index[y].empty() || X_index[y+1].empty()) continue; int q = 0; for(int p = 0; p < (int)X_index[y].size(); p++) { if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q])) { right_edge[X_index[y][p]].push_back(X_index[y+1][q]); left_edge[X_index[y+1][q]].push_back(X_index[y][p]); } while(q+1 < (int)X_begin[y+1].size() && X_begin[y+1][q+1] <= X_end[y][p]) { q++; if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q])) { right_edge[X_index[y][p]].push_back(X_index[y+1][q]); left_edge[X_index[y+1][q]].push_back(X_index[y][p]); } } } } X_max_index = curr_X_index; // cerr << "check7\n"; X_parent[1] = 0; X_dfs(1, 1); // cerr << "check8\n"; for(int u = 1; u <= X_max_index; u++) { right_reach[u] = X_index_size[u]; for(int v: right_edge[u]) { if(v == X_parent[u]) { X_delta[ make_pair(u, v) ] = N - X_subtree_sum[u]; X_delta[ make_pair(v, u) ] = N - (N - X_subtree_sum[u]); right_reach[u] += N - X_subtree_sum[u]; // cerr << "delta " << u << ' ' << v << " ;; " << X_delta[make_pair(u, v)] << '\n'; } else { right_reach[u] += X_subtree_sum[v]; X_delta[ make_pair(u, v) ] = X_subtree_sum[v]; X_delta[ make_pair(v, u) ] = (N - X_subtree_sum[v]); // cerr << "delta " << u << ' ' << v << " ;; " << X_delta[make_pair(u, v)] << '\n'; } } // cerr << u << ' ' << X_index_coord[u] << ' ' << X_index_size[u] << " : " << right_reach[u] << '\n'; } // cerr << "check9\n"; // for(int i = 0; i < N; i++) cerr << X[i] << ' ' << Y[i] << ' ' << right_reach[ point_X_line[i] ] << '\n'; vector<int> dist0(N, INF); dist0[0] = 0; queue<int> tbv; tbv.push(0); while(!tbv.empty()) { int u = tbv.front(); tbv.pop(); for(int z = 0; z < 4; z++) { int v = getIndex(X[u] + dx[z], Y[u] + dy[z]); if(v == -1) continue; if(dist0[v] <= dist0[u] + 1) continue; dist0[v] = dist0[u] + 1; tbv.push(v); } } for(int i = 0; i < N; i++) { // cerr << i << ' ' << X[i] << ' ' << Y[i] << " : " << dist0[i] << '\n'; init_dist += dist0[i]; } final_ans = init_dist; // cerr << "0 -> " << init_dist << '\n'; visit[0] = 1; dfs(0); // cerr << "delta 0 1 = " << delta[make_pair(0, 1)] << '\n'; final_ans = final_ans/2; return int(final_ans % 1'000'000'000LL); }