#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int dist[maxn][maxn], used[maxn];
int lf, rf, ftype[maxn], loc[maxn];
int n;
void extend_rf(int to)
{
used[to] = 1;
ftype[to] = 2;
loc[to] = loc[lf] + dist[lf][to];
for (int i = 0; i < n; i ++)
{
if (used[i])
continue;
if (dist[to][i] < dist[to][lf])
{
ftype[i] = 1;
used[i] = 1;
loc[i] = loc[to] - dist[to][i];
}
}
rf = to;
}
void extend_lf(int to)
{
used[to] = 1;
ftype[to] = 1;
loc[to] = loc[rf] - dist[rf][to];
for (int i = 0; i < n; i ++)
{
if (used[i])
continue;
if (dist[to][i] < dist[to][rf])
{
ftype[i] = 2;
used[i] = 1;
loc[i] = loc[to] + dist[to][i];
}
}
lf = to;
}
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
loc[0] = first;
ftype[0] = 1;
used[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;
}
lf = 0;
rf = 0;
extend_rf(closest);
int last = 0;
while(true)
{
int cnt = 0;
for (int i = 0; i < N; i ++)
cnt += used[i];
assert(cnt != last);
last = cnt;
bool done = true;
for (int i = 0; i < N; i ++)
if (!used[i])
{
done = false;
break;
}
if (done)
break;
int closest_lf = -1;
for (int i = 0; i < N; i ++)
{
if (used[i])
continue;
if (closest_lf == -1 ||
dist[lf][closest_lf] > dist[lf][i])
closest_lf = i;
///if (closest_rf == -1 ||
/// dist[rf][closest_rf] > dist[rf][i])
// closest_rf = i;
}
int ft = -1;
for (int i = 0; i < N; i ++)
{
if (!used[i] || ftype[i] == 1)
continue;
if (ft == - 1 || loc[i] < loc[ft])
ft = i;
}
int lf_loc = loc[lf] - (dist[lf][closest_lf] - 2 * dist[lf][ft]);
int rf_loc = loc[lf] + dist[lf][closest_lf];
int df = -1;
for (int i = 0; i < N; i ++)
{
if (!used[i] || ftype[i] == 2)
continue;
if (df == -1 || loc[i] > loc[df])
df = i;
}
int st_loc = loc[rf] - dist[rf][closest_lf];
int pt_loc = loc[rf] + (dist[rf][closest_lf] - 2 * dist[rf][df]);
if (st_loc == lf_loc)
extend_lf(closest_lf);
else
if (rf_loc == pt_loc)
extend_rf(closest_lf);
else
cout << "clown" << endl;
}
for (int i = 0; i < N; i ++)
stype[i] = ftype[i];
for (int i = 0; i < N; i ++)
location[i] = loc[i];
///for (int i = 0; i < N; i ++)
/// cout << location[i] << endl;
}
