#include "towns.h"
#define N 110
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int abs_(int a) { return a > 0 ? a : -a; }
int hubDistance(int n, int sub) {
static int ddu[N], ddv[N], ii[N], xx[N], yy[N];
int u, v, i, i_, j_, d_, r_, k1, k2, k3;
if (sub == 4)
return -1;
u = -1;
for (i = 0; i < n; i++) {
ddv[i] = i == 0 ? 0 : getDistance(0, i);
if (u == -1 || ddv[u] < ddv[i])
u = i;
}
v = -1;
for (i = 0; i < n; i++) {
ddu[i] = i == u ? 0 : getDistance(u, i);
if (v == -1 || ddu[v] < ddu[i])
v = i;
}
d_ = ddu[v];
for (i = 0; i < n; i++)
ddv[i] = i == v ? 0 : getDistance(v, i);
r_ = INF, i_ = -1, j_ = -1;
for (i = 0; i < n; i++) {
int r;
xx[i] = (d_ + ddu[i] - ddv[i]) / 2, yy[i] = (ddu[i] + ddv[i] - d_) / 2;
r = max(xx[i], d_ - xx[i]);
if (r_ > r)
r_ = r, i_ = -1, j_ = -1;
if (r_ == r) {
if (i_ == -1 || yy[i_] == yy[i])
i_ = i;
else
j_ = i;
}
ii[i] = i;
}
if (sub <= 2)
return r_;
k1 = 0, k2 = 0, k3 = 0;
for (i = 0; i < n; i++)
if (xx[i] < xx[i_])
k1++;
else if (xx[i] > xx[i_])
k3++;
else
k2++;
if (k1 * 2 > n || k3 * 2 > n) {
if (j_ == -1)
return -r_;
i_ = j_;
k1 = 0, k2 = 0, k3 = 0;
for (i = 0; i < n; i++)
if (xx[i] < xx[i_])
k1++;
else if (xx[i] > xx[i_])
k3++;
else
k2++;
if (k1 * 2 > n || k3 * 2 > n)
return -r_;
}
j_ = -1, k2 = 0;
for (i = 0; i < n; i++)
if (xx[i] == xx[i_]) {
if (j_ == -1 || getDistance(j_, i) != yy[i] + yy[j_])
j_ = i, k2++;
else if (--k2 == 0)
j_ = -1;
}
if (j_ == -1)
return r_;
k2 = 0;
for (i = 0; i < n; i++)
if (xx[i] == xx[i_] && getDistance(j_, i) != yy[i] + yy[j_])
k2++;
return k2 * 2 <= n ? r_ : -r_;
}
