HackerEarth Manhattan distance problem solution YASH PAL, 31 July 2024 In this HackerEarth Manhattan distance problem solution, There are N towns in a coordinate plane. Town i is located at coordinate (xi,yi). The distance between town i and town j is |xi – xj| + |yi – yj|. Your task is to compute the sum of the distance between each pair of towns. HackerEarth Manhattan distance problem solution. #include<bits/stdc++.h>using namespace std;#define F first#define S second#define pb push_back#define lb lower_bound#define ub upper_bound#define vi vector<int>#define all(x) x.begin(),x.end()#define fix fixed<<setprecision(10)#define rep(i,a,b) for(int i=int(a);i<=int(b);i++)#define repb(i,b,a) for(int i=int(b);i>=int(a);i--)#define FastIO ios_base::sync_with_stdio(0),cin.tie(0)typedef double db;typedef long long ll;const int N=2e5+5;const int mod=1e9+7;int n,x[N],y[N];void solve(){ cin>>n; rep(i,1,n) cin>>x[i]>>y[i]; sort(x+1,x+n+1); sort(y+1,y+n+1); ll ans=0,sumx=0,sumy=0; rep(i,1,n){ ans+=1ll*x[i]*(i-1)-sumx; ans+=1ll*y[i]*(i-1)-sumy; sumx+=x[i]; sumy+=y[i]; } cout<<ans<<'n';}signed main(){ FastIO; int t; cin>>t; while(t--) solve(); return 0;} Second solution #include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e6 + 14;int n, x[2][N];int main() { ios::sync_with_stdio(0), cin.tie(0); int t; cin >> t; while (t--) { cin >> n; ll ans = 0; for (int i = 0; i < n; ++i) cin >> x[0][i] >> x[1][i]; for (auto &c : x) { sort(c, c + n); for (int i = 0; i < n; ++i) ans += c[i] * (ll) i - c[i] * ll(n - i - 1); } cout << ans << 'n'; }} coding problems