#include "towns.h"
#include <bits/stdc++.h>
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define ff first
#define ss second
#define pii pair<int,int>
#define INF 1000010*110
const int MAXN = 120 ;
using namespace std;
int m[MAXN][MAXN] ;
int d[MAXN] ;
void ini()
{
lp(i,0,MAXN) lp(j, 0 , MAXN) m[i][j] = -1 ;
}
int query(int A ,int N)
{
pii p = pii(-1,-1) ;
lp(i,0,N)
{
if( i == A ) continue ;
m[A][i] = getDistance(A,i) ;
if(m[A][i]>p.ss) p = pii( i , m[A][i] ) ;
}
return p.ff ;
}
int hubDistance( int N , int sub )
{
ini();
int B = query(0 , N) ;
int C = query(B , N) ;
query(C , N) ;
int R = INF , esq = 0 , dir = 0 , meio = 0, antigo, cara = B;
lp(i,0,N)
if(i!=C and i!=B)
{
int b = (m[B][i]+m[C][i] - m[B][C])/2 ;
d[i] = b ;
antigo=R;
R = min( R , max( m[B][i] , m[C][i] ) - b ) ;
if(R<antigo) cara = m[B][i]>m[C][i] ? B : C ;
}
if(sub == 1 or sub == 2) return R ;
d[B] = d[C] = 0 ;
lp(i,0,N)
{
if(d[i]!=0) { meio++ ; continue; }
if(m[cara][i]<R) esq++ ;
else if(m[cara][i]>R) dir++ ;
}
if(meio>N/2 or esq>N/2 or dir>N/2) return -R ;
return R ;
}
