#include "towns.h"
#include <stdio.h>
#include <string.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 dd[N][N];
int getDistance_(int i, int j) {
if (dd[i][j] == -1)
dd[i][j] = dd[j][i] = getDistance_(i, j);
return dd[i][j];
}
int hubDistance(int n, int sub) {
static int ddu[N], ddv[N], ii[N], xx[N], yy[N], kk[N];
int u, v, i, i_, j_, d_, r_, k1, k2, k3;
for (i = 0; i < n; i++)
memset(dd[i], -1, n * sizeof *dd[i]), dd[i][i] = 0;
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 || xx[i_] == xx[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_;
}
if (sub == 4)
return k2 * 2 <= n ? r_ : -r_;
memset(kk, 0, n * sizeof *kk);
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_]) {
if (j_ == -1)
j_ = i;
k2++, kk[j_]++;
} else {
kk[i]++;
if (--k2 == 0)
j_ = -1;
}
}
if (j_ == -1)
return r_;
k2 = 0;
for (i = 0; i < n; i++)
if (kk[i] > 0 && (i == j_ || getDistance_(j_, i) != yy[i] + yy[j_]))
k2 += kk[i];
return k2 * 2 <= n ? r_ : -r_;
}
