#include "rail.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int dist[5000][5000];
int ans[5000][2];
int n;
int cmp(int i, int j){
return dist[i][0]<dist[j][0];
}
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
stype[0]=1;
location[0]=first;
for(int i=0;i<N;i++){dist[i][i]=0;
for(int j=i+1;j<N;j++){
dist[i][j]=getDistance(i,j);
dist[j][i]=dist[i][j];
}
}
vector<int> med[n];
for(int i=1;i<N;i++){
for(int j=1;j<N;j++){
if(i!=j && dist[0][i]==dist[0][j]+dist[i][j]){
med[i].push_back(j);
}
}
sort(med[i].begin(),med[i].end());
/*for(int j=0;j<med[i].size();j++)cout<<med[i][j]<<" ";
cout<<endl;*/
}
for(int i=1;i<N;i++){
if(med[i].size()==0){
location[i]=dist[0][i]+location[0];
stype[i]=2;
}
}
for(int i=1;i<N;i++){
if(med[i].size()==1){
location[i]=location[med[i][0]]-dist[med[i][0]][i];
stype[i]=1;
}
}
for(int i=1;i<N;i++){
if(med[i].size()==2){
location[i]=location[med[i][0]]+dist[med[i][0]][i];
stype[i]=2;
}
}
//for(int i=0;i<N;i++)cout<<location[i]<<endl;
/*int D=1;
for(int i=1;i<N;i++){
if(dist[0][i]<dist[0][D]){
D=i;
}
}
for(int i=1;i<N;i++){
if(dist[0][i]==dist[0][D]+dist[D][i]){
stype[i]=1;
location[i]=first+dist[0][D]-dist[D][i];
}else{
stype[i]=2;
location[i]=first+dist[0][i];
}
}
stype[D]=2;
location[D]=dist[0][D]+first;
stype[0]=1;
location[0]=first;*/
}
