#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 5000;
static int n;
bool fix[nmax + 1];
int v[nmax + 1], tip[nmax + 1];
pair<int, int> mn[nmax + 1];
int d[nmax + 1][nmax + 1];
void recalc (int x) {
mn[x] = {1 << 30, -1};
for (int i = 0; i < n; ++ i) {
if (fix[i] == 0 && d[x][i] < mn[x].first) {
mn[x] = {d[x][i], i};
}
}
}
void findLocation(int N, int first, int location[], int stype[]) {
for (int i = 0; i < N; ++ i)
for (int j = i + 1; j < N; ++ j) {
int x = getDistance(i, j);
d[i][j] = d[j][i] = x;
}
n = N;
v[0] = first;
tip[0] = 1;
fix[0] = 1;
recalc(0);
for (int step = 0; step < N - 1; ++ step) {
int x, y, e = 1 << 30;
x = y = -1;
for (int i = 0; i < N; ++ i) {
if (fix[i] == 1) {
if (mn[i].first < e) {
x = i;
y = mn[i].second;
e = mn[i].first;
}
}
}
if (tip[x] == 1) {
v[y] = v[x] + e;
tip[y] = 2;
} else {
v[y] = v[x] - e;
tip[y] = 1;
}
fix[y] = 1;
recalc(x);
recalc(y);
}
for (int i = 0; i < N; ++ i) {
location[i] = v[i];
stype[i] = tip[i];
}
}
