HackerRank Geometry – Meeting Point

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

Cerinta

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 sursa

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