#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
map<ii, int> M;
int dist(int a, int b) {
if(a > b) swap(a, b);
if(M.count({a, b}))
return M[{a, b}];
return M[{a, b}] = getDistance(a, b);
}
void findLocation(int N, int first, int location[], int stype[]) {
stype[0] = 1;
location[0] = first;
int b = 1;
for(int i = 2 ; i < N ; i++)
if(dist(0, i) < dist(0, b))
b = i;
stype[b] = 2;
location[b] = location[0] + dist(0, b);
vector<int> lst;
lst.push_back(b);
int fst = 0;
vector<ii> cand;
for(int i = 0 ; i < N ; i++) {
if(i == 0 || i == b)
continue;
int d0 = dist(0, i);
int db = dist(b, i);
int d = dist(0, b);
if(d0 - db == d) {
if(db < d)
cand.push_back({d0, i});
} else
cand.push_back({d0, i});
}
sort(cand.begin(), cand.end());
for(auto p : cand) {
int d = dist(0, lst.back());
int w = p.Y;
int dlst = dist(lst.back(), w);
bool ins = true;
if(dlst >= d)
ins = false;
else {
int ind = 0;
while(dist(lst[ind], 0) < d - dlst)
ind++;
if(dist(lst[ind], 0) == d - dlst)
ins = false;
else {
if(dist(0, lst[ind]) + (dist(0, lst[ind]) + dlst - d) != dist(0, w))
ins = false;
}
}
if(ins) {
stype[w] = 1;
location[w] = location[lst.back()] - dlst;
} else {
stype[w] = 2;
location[w] = location[0] + dist(0, w);
lst.push_back(w);
}
}
//~ int a = 0;
//~ for(int i = 1 ; i < N ; i++)
//~ if(i != b)
//~ if(dist(b, i) < dist(b, a))
//~ a = i;
//~ stype[a] = 1;
//~ location[a] = location[b] - dist(b, a);
}
