#include "towns.h"
using namespace std;
#include <map>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
int rez[225][5];
int distdiam[225];
int getmax(int n,int b,int id)
{
int best=-1,can=0;
for(int i=0; i<n; i++)
{
rez[i][id]=getDistance(b,i);
if(rez[i][id]>best)
{
best=rez[i][id];
can=i;
}
}
return can;
}
map<int,int>mp;
map<int,vector<int>>noduri;
int majoritar(vector<int>vec,int nmax)
{
int can=vec[0],off=1;
for(int i=1; i<vec.size(); i++)
{
if(getDistance(can,vec[i])==distdiam[can]+distdiam[vec[i]])
{
off--;
if(off<0)
{
can=vec[i];
off=1;
}
}
else
{
off++;
}
}
off=0;
for(int i=0; i<vec.size(); i++)
{
if(getDistance(can,vec[i])!=distdiam[can]+distdiam[vec[i]]){
off++;
}
}
if(off>nmax)
{
return 1;
}
return 0;
}
int hubDistance(int N, int sub)
{
mp.clear();
noduri.clear();
int d1=getmax(N,1,0);
int d2=getmax(N,d1,1);
int d3=getmax(N,d2,2);
int dab=rez[d2][1];
int minim=1000000000;
for(int i=0; i<N; i++)
{
if(i!=d1 && i!=d2)
{
int distodim=(rez[i][1]+rez[i][2]-dab)/2;
distdiam[i]=distodim;
int x=(rez[i][1]-distodim);
int y=(rez[i][2]-distodim);
int diff=x-y;
mp[diff]++;
noduri[diff].push_back(i);
minim=min(minim,abs(diff));
}
}
int prefix=1;
int semn=-1;
int r=(dab+minim)/2;
int nmax=N/2;
for(auto it:mp)
{
if(abs(it.first)==(minim))
{
if(it.second<=nmax && prefix<=nmax && N-prefix-it.second<=nmax)
{
semn=1;
}
else if(sub!=2 && sub!=4 && prefix<=nmax && N-prefix-it.second<=nmax)
{
if(majoritar(noduri[it.first],nmax)==0)
{
semn=1;
}
}
}
prefix=prefix+it.second;
noduri[it.first].clear();
}
noduri.clear();
return r*semn;
}
