### Metro Land is a country located on a 2D Plane. They are having a summer festival for everyone in the country and would like to minimise the overall cost of travel for their citizens. Costs of travel are calculated as follows:

### Determine the total cost of travel for all citizens to go to the festival at that location.

**Complete Question**

### Approach

Repeat the coordinates in x points array and y points array according to the numsPoint array.

x1 = Take median of all the x axis points.

y1 = Take median of all the y axis points.

### Solution

```
int cost(x, y, a, b) {
return (abs(x-a)+abs(y-b));
}
int greedy(vector<int> numpeople, vector<int> x, vector<int> y){
vector<int> xx, yy;
int ans = 0;
for(int i = 0 ; i < numpeople.size();i++){
int count = numpeople[i];
while(count--){
xx.push_back(x[i]);
yy.push_back(y[i]);
}
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
int mx, my;
mx = xx[xx.size() / 2];
my = yy[yy.size() / 2];
for(int i = 0; i < numpeople.size(); i++){
ans += numpeople[i] * cost(mx, my, x[i], y[i]);
}
return ans;
}
```

The solution is of O(n^2) time complexity.

I think the complexity is O(n*p) where n is the number of city and p is the max people in a city

I get your point but it can’t be less than O(nlogn) as sorting is included.

It should be median not average, please correct the same.

Yes. The code is correct. I have changed it to median in the theory.