#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
void findLocation(int n, int first, int location[], int stype[]) {
for (int i = 0;i < n;i++) {
location[i] = -1;
stype[i] = -1;
}
location[0] = first;
stype[0] = 1;
int dist[n][n];
for (int i = 0;i < n;i++) {
for (int j = i;j < n;j++) {
if (i == j) {
dist[i][j] = INT_MAX;
continue;
}
dist[i][j] = dist[j][i] = getDistance(i, j);
}
}
int curr = 0;
bool border = false;
int cnt = 1;
while (!border) {
int absolute_mn = INT_MAX, absolute_mnd = -1;
for (int i = 0;i < n;i++) {
if (dist[curr][i] < absolute_mn) {
absolute_mn = dist[curr][i];
absolute_mnd = i;
}
}
int mn = INT_MAX, mnd = -1;
for (int i = 0;i < n;i++) {
if (location[i] != -1) continue;
if (dist[curr][i] < mn && dist[curr][i] != dist[curr][absolute_mnd] + dist[absolute_mnd][i]) {
mn = dist[curr][i];
mnd = i;
}
}
if (mnd == -1) {
curr = absolute_mnd;
border = true;
break;
}
if (stype[curr] == 1) {
location[mnd] = location[curr] + mn;
}
else {
location[mnd] = location[curr] - mn;
}
stype[mnd] = 3 - stype[curr];
cnt++;
curr = mnd;
}
vector <pair <int, int>> close;
for (int i = 0;i < n;i++) {
if (location[i] != -1) continue;
close.push_back({dist[curr][i], i});
}
if (close.size() == 0) return;
sort(close.begin(), close.end());
if (stype[curr] == 1) {
location[close[0].ss] = location[curr] + close[0].ff;
}
else {
location[close[0].ss] = location[curr] - close[0].ff;
}
stype[close[0].ss] = 3 - stype[curr];
int ls = close[0].ss;
for (int i = 1;i < close.size();i++) {
if (dist[curr][close[i].ss] == dist[curr][ls] + dist[ls][close[i].ss]) {
if (stype[curr] == 1) {
location[close[i].ss] = location[curr] + dist[curr][ls] - dist[ls][close[i].ss];
}
else {
location[close[i].ss] = location[curr] - dist[curr][ls] + dist[ls][close[i].ss];
}
stype[close[i].ss] = 3 - stype[curr];
}
else {
if (stype[curr] == 1) {
location[close[i].ss] = location[curr] + close[i].ff;
}
else {
location[close[i].ss] = location[curr] - close[i].ff;
}
stype[close[i].ss] = 3 - stype[curr];
ls = close[i].ss;
}
}
}
