Practice

MEDIUM

# PREREQUISITES:

Geometry, Manhattan distance.

# PROBLEM:

Given a set of N points and constants a and b, calculate the sum of the distances between each pair of points. However, the distance between 2 points is defined as max(a × |x1 - x2|, b × |y1 - y2|)

# EXPLANATION:

Transform each coordinate (x, y) into (\frac{a * x + b * y}{2} , \frac{a * x - b * y}{2} ).

• Calculate the distance between all pairs of points using the Manhattan distance on the new coordinates.
• # SOLUTIONS:

Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{

ll int t;
cin >> t;
while (t--)
{
ll int n;
cin >> n;
int a, b;
cin >> a >> b;
vector<ll int> pointx;
vector<ll int> pointy;

ll int x, y;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
pointx.push_back(x);
pointy.push_back(y);
}

ll int sum = 0;
for (ll int i = 0; i < n - 1; i++)
{
for (ll int j = i + 1; j < n; j++)
{

sum += max((a * abs(pointx[i] - pointx[j])), (b * abs(pointy[i] - pointy[j])));
}
}

cout << sum << endl;
}
return 0;
}