#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 5505;
int dist[Nmax][Nmax];
bool used[Nmax];
void findLocation(int N, int F, int location[], int stype[])
{
int i, j, n = N;
for(i=0; i<n; ++i)
{
dist[i][i] = 1e9;
for(j=i+1; j<n; ++j)
dist[i][j] = dist[j][i] = getDistance(i, j);
}
int X = 0, Y = 0;
for(i=0; i<n; ++i)
if(dist[0][i] < dist[0][Y]) Y = i;
for(i=0; i<n; ++i)
if(dist[Y][i] < dist[X][Y]) X = i;
used[X] = used[Y] = 1;
location[Y] = F + dist[0][Y];
location[X] = location[Y] - dist[X][Y];
stype[X] = 1; stype[Y] = 2;
int lastst1, lastst2, lastdr1, lastdr2;
lastdr1 = X; lastdr2 = Y;
lastst1 = X; lastst2 = Y;
for(i=0; i<n-2; ++i)
{
int k = 0;
for(j=0; j<n; ++j)
if(!used[j] && dist[j][X] < dist[k][X]) k = j;
used[k] = 1;
if(dist[k][X] < dist[k][Y]) /// e in dreapta
{
if(dist[k][lastdr2] == dist[k][lastdr1] + dist[lastdr2][lastdr1]) /// e 2
{
location[k] = location[X] + dist[X][k];
stype[k] = 2;
if(location[k] > location[lastdr2]) lastdr2 = k;
}
else
{
stype[k] = 1;
for(j=0; j<n; ++j)
if(used[j] && stype[j] == 2 && location[j] >= location[Y] && dist[k][X] == dist[k][j] + dist[j][X])
location[k] = location[j] - dist[j][k];
if(location[k] > location[lastdr1]) lastdr1 = k;
}
}
else /// e in stanga
{
if(dist[k][lastst1] == dist[k][lastst2] + dist[lastst1][lastst2]) /// e 1
{
location[k] = location[Y] - dist[Y][k];
stype[k] = 1;
if(location[k] < location[lastst1]) lastst1 = k;
}
else
{
stype[k] = 2;
for(j=0; j<n; ++j)
if(used[j] && stype[j] == 1 && location[j] <= location[X] && dist[k][Y] == dist[k][j] + dist[j][Y])
location[k] = location[j] + dist[j][k];
if(location[k] > location[lastst2]) lastst2 = k;
}
}
}
}
