Soluție HackerRank pentru Meeting Point, subdomeniul Geometry, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Meeting Point
  • Domeniu: Geometry
  • Limbaj: C++14

Challenge: Meeting Point

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464758985

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/meeting-point/problem

Cerință

There is an infinite integer grid where  N people live in N different houses. They decide to create a meeting point at one person's house. 

From any given cell, all 8 adjacent cells can be reached in 1 unit of time, e.g. (x,y) can be reached from (x-1,y+1) in one unit of time. Find a common meeting place which minimizes the combined travel time of everyone.

Input Format
A positive integer N that denotes N houses or people.

The following *N* lines will contain two integers x,y each that denote the coordinates of the respective house.

Output Format
An integer, M, that denotes the minimum combined travel time of everyone.


Constraints
N <= 10<sup>5</sup>
The absolute value of each co-ordinate in the input will be at most 10<Sup>9</sup>

HINT: You may need 64-bit integer.

Input #1
<pre>
4
0 1
2 5
3 1
4 0
</pre>

Output #1
<pre>
8
</pre>

Explanation
The houses will have a travel-sum of 11, 13, 8, or 10. 8 is the minimum.

Input #2
<pre>
6
12 -14
-3 3
-14 7
-14 -3
2 -12
-1 -6
</pre>

Output #2:
<pre>54</pre>

Cod sursă

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int64> x(n), y(n), u(n), v(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        u[i] = x[i] + y[i];
        v[i] = x[i] - y[i];
    }

    vector<int64> costU(n, 0), costV(n, 0);

    auto accumulateCost = [&](const vector<int64>& arr, vector<int64>& out) {
        vector<pair<int64, int>> p;
        p.reserve(n);
        for (int i = 0; i < n; ++i) p.push_back({arr[i], i});
        sort(p.begin(), p.end());

        vector<int64> pref(n, 0);
        pref[0] = p[0].first;
        for (int i = 1; i < n; ++i) pref[i] = pref[i - 1] + p[i].first;

        for (int i = 0; i < n; ++i) {
            int64 val = p[i].first;
            int64 left = val * i - (i ? pref[i - 1] : 0);
            int64 right = (pref[n - 1] - pref[i]) - val * (n - 1 - i);
            out[p[i].second] = left + right;
        }
    };

    accumulateCost(u, costU);
    accumulateCost(v, costV);

    int64 best = LLONG_MAX;
    for (int i = 0; i < n; ++i) {
        int64 total = (costU[i] + costV[i]) / 2; // Chebyshev distance sum
        if (total < best) best = total;
    }

    cout << best << '\n';
    return 0;
}
HackerRank Geometry – Meeting Point