#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3;
int n, dis[N][N];
void findLocation(int NN, int first, int location[], int stype[]) {
n = N;
for (int i = 0; i < n; i++) {
dis[i][i] = 0;
for (int j = i+1; j < n; j++) {
dis[i][j] = dis[j][i] = getDistance(i, j);
}
}
/*
encuentro la estacion mas próxima, estara a la derecha y será x
para cualquier otra estación, o bien pasará por x y luego irá hacia la izquierda
o bien será ir solo hacia la derecha
*/
int x = 1;
int mn = dis[0][1];
for (int i = 2; i < n; i++) {
if (dis[0][i] < mn) {
mn = dis[0][i];
x = i;
}
}
stype[0] = 1;
location[0] = first;
stype[x] = 2;
location[x] = first + dis[0][x];
for (int i = 1; i < n; i++) {
if (i == x) continue;
if (dis[0][i] == dis[0][x] + dis[x][i]) {
stype[i] = 1;
location[i] = location[x] - dis[x][i];
}
else {
stype[i] = 2;
location[i] = first + dis[0][i];
}
}
}
