#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const int M = 1000005;
int dist[N][N];
int distNow[N];
int* location;
int* stype;
int n;
int cdist(int i, int j)
{
if (i == j) return 0;
if (dist[i][j] == 0)
{
dist[i][j] = getDistance(i, j);
dist[j][i] = dist[i][j];
}
return dist[i][j];
}
int getNext(int x)
{
int mi = M;
int next = -1;
for (int i = 0; i < n; i++)
{
if (cdist(x, i) < mi && i != x)
{
mi = cdist(x, i);
next = i;
}
}
if (next != -1)
{
if (stype[x] == 1)
{
location[next] = location[x] + mi;
stype[next] = 2;
} else
{
location[next] = location[x] - mi;
stype[next] = 1;
}
}
return next;
}
void makeNew()
{
for (int i = 0; i < N; i++)
{
distNow[i] = M;
}
}
void findLocation(int n1, int first, int location1[], int stype1[])
{
n = n1;
location = location1;
stype = stype1;
location[0] = first;
stype[0] = 1;
if (n == 1) return;
int l = 0;
int cur = getNext(l);
l = getNext(cur);
makeNew();
while (true)
{
int cur = getNext(l);
int cl = -1;
int mi = M;
for (int i = 0; i < n; i++)
{
distNow[i] = min(distNow[i], cdist(l, i));
if (cdist(cur, i) < mi && cdist(cur, i) > cdist(l, cur) && distNow[i] > cdist(cur, i))
{
cl = i;
mi = cdist(cur, i);
}
}
if (cl == -1)
{
break;
} else
{
l = cl;
location[l] = location[cur] - mi;
stype[l] = 1;
}
}
int ml = l;
int r = getNext(ml);
makeNew();
while (true)
{
int cur = getNext(r);
int cr = -1;
int mi = M;
for (int i = 0; i < n; i++)
{
distNow[i] = min(distNow[i], cdist(r, i));
if (cdist(cur, i) < mi && cdist(cur, i) > cdist(r, cur) && distNow[i] > cdist(cur, i))
{
cr = i;
mi = cdist(cur, i);
}
}
if (cr == -1)
{
break;
} else
{
r = cr;
location[r] = location[cur] + mi;
stype[r] = 2;
}
}
int mr = r;
l = getNext(r);
makeNew();
while (true)
{
int cur = getNext(l);
int cl = -1;
int mi = M;
for (int i = 0; i < n; i++)
{
distNow[i] = min(distNow[i], cdist(l, i));
if (cdist(cur, i) < mi && cdist(cur, i) > cdist(l, cur) && distNow[i] > cdist(cur, i))
{
cl = i;
mi = cdist(cur, i);
}
}
if (cl == -1)
{
break;
} else
{
l = cl;
location[l] = location[cur] - mi;
stype[l] = 1;
}
}
}
