SQMA03-Editorial

editorial
1

PROBLEM LINK:

Practice

DIFFICULTY:

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;
}