#include <bits/stdc++.h> using namespace std; const int Mod = 1e9, Nmax = 1e5 + 5; typedef long long ll; int n, x[Nmax], y[Nmax], w[Nmax]; vector<int> edge[Nmax], v[Nmax]; void dfs(int node, int dad = 0) { for(auto it : edge[node]) if(it != dad) { dfs(it, node); w[node] += w[it]; w[node] %= Mod; } } void add_edge(set< pair<int,int> > &Edges, int x, int y) { if(Edges.find({x, y}) != Edges.end()) return; edge[x].push_back(y); edge[y].push_back(x); Edges.insert({x, y}); } int calc_dist() /// vertical { int i, j; map< pair<int,int> , int > where; set< pair<int,int> > Edges; int nr = 0; for(i=1; i<=n; ++i) w[i] = 0, edge[i].clear(), v[i].clear(); for(i=0; i<n; ++i) v[x[i]].push_back(y[i]); for(i=1; i<=n; ++i) { sort(v[i].begin(), v[i].end()); for(j=0; j<v[i].size(); ++j) { if(!j || v[i][j] != v[i][j-1] + 1) ++nr; where[{i, v[i][j]}] = nr; w[nr] ++; } } for(i=1; i<=n; ++i) for(auto it : v[i]) if(where[{ i+1, it }]) add_edge(Edges, where[{ i+1, it }], where[{ i, it }]); dfs(1); ll ans = 0; for(i=1; i<=nr; ++i) { ans += (ll) w[i] * (w[1] - w[i]); ans %= Mod; } return ans; } int DistanceSum(int N, int *X, int *Y) { int i, xmin = 2e9, ymin = 2e9; n = N; for(i=0; i<N; ++i) { x[i] = X[i]; y[i] = Y[i]; xmin = min(xmin, x[i]); ymin = min(ymin, y[i]); } for(i=0; i<N; ++i) x[i] -= xmin - 1, y[i] -= ymin - 1; int ans = calc_dist(); for(i=0; i<n; ++i) swap(x[i], y[i]); ans += calc_dist(); return ans % Mod; }

city.cpp: In function 'int calc_dist()':
city.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<v[i].size(); ++j)
                  ~^~~~~~~~~~~~