#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int dist[maxn][maxn], used[maxn];
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
if (N == 1)
return;
for (int i = 0; i < N; i ++)
for (int j = i + 1; j < N; j ++)
{
dist[i][j] = dist[j][i] = getDistance(i, j);
}
int closest = -1;
for (int i = 1; i < N; i ++)
{
if (closest == -1 || dist[0][closest] > dist[0][i])
closest = i;
}
location[closest] = location[0] + dist[0][closest];
stype[0] = 1;
stype[closest] = 2;
int left = 0, right = closest;
used[left] = used[right] = 1;
int cnt = 2;
while(cnt < N)
{
int closest_left = -1;
int closest_right = -1;
for (int i = 0; i < N; i ++)
{
if (used[i])
continue;
if (closest_left == -1 ||
dist[left][closest_left] > dist[left][i])
closest_left = i;
if (closest_right == -1 ||
dist[right][closest_right] > dist[right][i])
closest_right = i;
}
if (closest_left != closest_right)
{
used[closest_left] = used[closest_right] = 1;
location[closest_left] = location[left] + dist[left][closest_left];
location[closest_right] = location[right] - dist[right][closest_right];
stype[closest_left] = 2;
stype[closest_right] = 1;
right = closest_left;
left = closest_right;
cnt = cnt + 2;
}
else
{
int vertex = closest_left;
used[vertex] = 1;
cnt ++;
if (dist[left][vertex] < dist[right][vertex])
{
location[vertex] = location[left] + dist[left][vertex];
stype[vertex] = 2;
right = vertex;
}
else
{
location[vertex] = location[right] - dist[right][vertex];
stype[vertex] = 1;
left = vertex;
}
}
}
}
