#include <iostream>
#include <vector>
#include <algorithm>
#include "rail.h"
using namespace std;
int dis1[10000];
int sp;
int dis2[10000];
int sta[10000];
int mnd;
struct pla{
int x, y;
};
vector<pla> lef;
vector<pla> rig;
bool cmp1(const pla &a, const pla&b){
return a.y > b.y;
}
bool cmp2(const pla &a, const pla&b){
return a.y < b.y;
}
int getDistance(int i, int j);
void findLocation(int n, int first, int location[], int stype[]){
location[0] = first;
stype[0]=1;
sp = 0;
sta[0] = 2;
mnd = 100000000;
for(int i=1; i<n; i++){
dis1[i] = getDistance(0, i);
if(dis1[i]<mnd){sp = i; mnd = dis1[i];}
}
location[sp] = first + dis1[sp];
stype[sp]=2;
sta[sp] = 2;
mnd = 100000000;
for(int i=1; i<n; i++){
if(i!=sp){
dis2[i] = getDistance(sp, i);
if(dis1[i] == dis2[i] + dis1[sp]){
if(dis2[i]<dis1[sp]){sta[i] = 2; location[i] = location[sp] - dis2[i]; stype[i] = 1;}
else {sta[i] = 1;}
}
else {sta[i] = 3;}
}
}
for(int i=1; i<n; i++){
if(sta[i]==1){
lef.push_back({i, dis2[i]});
}
if(sta[i]==3){
rig.push_back({i, dis1[i]});
}
}
sort(rig.begin(), rig.end(), cmp2);
sort(lef.begin(), lef.end(), cmp2);
int cur = sp;
for(const auto &inf : rig){
int n1 = inf.x;
int n2 = inf.y;
if(cur==sp){
location[n1] = first + n2;
stype[n1] = 2;
cur = n1;
}
else {
int n3 = getDistance(cur, n1);
if(n2 == n3 + dis1[cur]){
location[n1] = location[cur] - n3;
stype[n1] = 1;
}
else {
location[n1] = first + n2;
stype[n1] = 2;
cur = n1;
}
}
}
cur = 0;
for(const auto &inf : lef){
int n1 = inf.x;
int n2 = inf.y;
if(cur==0){
location[n1] = location[sp] - n2;
stype[n1] = 1;
cur = n1;
}
else {
int n3 = getDistance(cur, n1);
if(n2 == n3 + dis1[cur]){
location[n1] = location[cur] + n3;
stype[n1] = 2;
}
else {
location[n1] = location[sp] - n2;
stype[n1] = 1;
cur = n1;
}
}
}
}
