#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; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N], yy[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int hubDistance(int n, int sub) {
static int ddu[N], ddv[N], ii[N];
int u, v, i, i_, j_, d_, r_, k1, k2, k3;
u = -1;
for (i = 0; i < n; i++) {
ddv[i] = getDistance(0, i);
if (u == -1 || ddv[u] < ddv[i])
u = i;
}
v = -1;
for (i = 0; i < n; i++) {
ddu[i] = getDistance(u, i);
if (v == -1 || ddu[v] < ddu[i])
v = i;
}
d_ = ddu[v];
u = -1;
for (i = 0; i < n; i++)
ddv[i] = 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)
i_ = i;
else
j_ = i;
}
ii[i] = i;
}
sort(ii, 0, n);
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_;
}
return (k2 - 1) * 2 <= n ? r_ : -r_;
}
