#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
int cache[MAXN][MAXN];
int dist(int a, int b) {
if (a > b) swap(a, b);
if (a == b) return 0;
if (cache[a][b] != 0) return cache[a][b];
return cache[a][b] = getDistance(a, b);
}
int hubDistance(int n, int sub) {
int r = 1e9;
if (sub == 1) {
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
map<pair<int, int>, int> mx_dist;
for (int k=0; k<n; k++) {
if (k == i or k == j) continue;
int a = (dist(i, k) + dist(j, k) - dist(i, j)) / 2;
int x = dist(i, k) - a;
int y = dist(j, k) - a;
// // cerr << i << ' ' << j << ' ' << k << ':' << a << ' ' << x << ' ' << y << endl;
mx_dist[{x, y}] = max({mx_dist[{x, y}], a, x, y});
}
int pf[(int)mx_dist.size()+1]; pf[0] = 0; int pf_i = 1;
int last_x = 0;
for (auto it=mx_dist.begin(); it != mx_dist.end(); it++, pf_i++) {
auto [x, y] = it->first;
int mx = it->second;
pf[pf_i] = max(mx, x-last_x + pf[pf_i-1]);
last_x = x;
}
int sf[(int)mx_dist.size()+1]; sf[(int)mx_dist.size()] = 0; int sf_i = (int)mx_dist.size()-1;
int last_y = 0;
for (auto it = mx_dist.end(); it != mx_dist.begin(); sf_i--) {
it--;
auto [x, y] = it->first;
int mx = it->second;
sf[sf_i] = max(mx, y-last_y + sf[sf_i+1]);
last_y = y;
}
int pt = 0;
for (auto it=mx_dist.begin(); it != mx_dist.end(); it++, pt++) {
int mx = max({it->second, pf[pt+1], sf[pt]});
r = min(r, mx);
// cerr << i << ' ' << j << ':' << mx << endl;
}
}
}
}
return r;
}
