#include <stdio.h>
#include "rail.h"
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int d[5000][5000];
int getDist(int i,int j) {
if (i == j) return 0;
if (!d[i][j])
d[i][j] = d[j][i] = getDistance(i,j);
return d[i][j];
}
void findLocation(int N, int first, int location[], int stype[])
{
int i; location[0] = first; stype[0] = 1;
vector<pii > v; int rc=0;
int fi = 0; int mn = 1e9;
for (i = 1; i < N; ++i) {
int d = getDist(0, i);
if (mn > d) {
mn = d;
fi = i;
}
}
location[fi] = first + mn;
stype[fi] = 2;
for (i = 1; i < N; ++i) {//find closest C
if (i == fi) continue;
int dist = getDist(fi,i);
if (getDist(0, i) > dist && dist < getDist(0, fi)
&& getDist(0, i) - getDist(0, fi) == dist) {
stype[i] = 1;
location[i] = location[fi] - dist;
if (location[rc] < location[i]) rc = i;
}
else v.push_back({getDist(i,0),i});
}
sort(v.begin(), v.end());
int r = -1,l=-1;
for (auto p : v) {
int x = p.second;
d[rc][x] = d[x][rc] = getDist(0, x) - (location[rc]-location[0]);
//printf("x:%d,%d\n", x,d[rc][x]);
if (getDist(rc, x) < getDist(x, fi)) {
if (r > 0 && getDist(rc, x) == getDist(x, r) + getDist(rc, r)) {
stype[x] = 1;
location[x] = location[r] - getDist(r,x);
}
else {
r = x;
stype[x] = 2;
location[x] = location[rc]+getDist(rc,x);
}
}
else {
if (l > 0 && getDist(fi, x) == getDist(l, x) + getDist(fi, l)) {
stype[x] = 2;
location[x] = location[l] + getDist(l,x);
}
else {
l = x;
stype[x] = 1;
location[x] = location[fi] - getDist(fi,x);
}
}
}
}
