#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define cerr if(false) cerr
#endif
template< class T, class T2 > inline bool chkmax( T& a, const T2& b ){ return a < b ? a = b, 1 : 0 ; };
template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0 ; };
#define out(x) #x << " = " << x << " "
typedef long long ll;
const int MAX_N = 128;
const ll inf = 1e18;
int n;
int hubDistance(int N, int sub) {
n = N;
ll mxDist = -1;
int d1, d2;
for( int i=0 ; i < n ; i++ ){
if( i == 0 ) continue;
ll currDist = getDistance( 0, i );
if( chkmax( mxDist, currDist ) ) d1 = i;
}
mxDist = -1;
for( int i=0 ; i < n ; i++ ){
if( i == d1 ) continue;
ll currDist = getDistance( d1, i );
if( chkmax( mxDist, currDist ) ) d2 = i;
}
ll distDiam = getDistance( d1, d2 );
//cerr << out( d1 ) << out( d2 ) << out( getDistance( d1, d2 ) ) << endl;
ll nas = inf;
for( int i=0 ; i < n ; i++ ){
if( i == d1 || i == d2 ) continue;
ll dist1 = getDistance( i, d1 );
ll dist2 = getDistance( i, d2 );
ll diff = abs( dist1 - dist2 );
ll currNas = ( distDiam - diff ) / 2LL + diff;
chkmin( nas, currNas );
}
cerr << out( nas ) << endl;
return -nas;
}
