#include "towns.h"
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int hubDistance(int N, int sub) {
vector<int> d1(N);
for (int i = 0; i < N; ++i) {
d1[i] = getDistance(0, i);
}
int x = max_element(d1.begin(), d1.end()) - d1.begin();
vector<int> dx(N);
for (int i = 0; i < N; ++i) {
dx[i] = getDistance(x, i);
}
int y = max_element(dx.begin(), dx.end()) - dx.begin();
vector<int> dy(N);
for (int i = 0; i < N; ++i) {
dy[i] = getDistance(y, i);
}
int d = dy[x];
int R = 1e9;
int ans = 0;
for (int i = 0; i < N; ++i) {
int distance_to_path = (dx[i] + dy[i] - d) / 2;
int v1 = dx[i] - distance_to_path;
int v2 = dy[i] - distance_to_path;
if (v2 < v1) swap(v1, v2);
if (v2 - v1 < R) {
R = v2 - v1;
ans = v2;
}
}
return ans;
}
