#include "rail.h"
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
std::ofstream out ("data.out");
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 5000;
int const inf = 1000000000;
std::map<std::pair<int,int>, int> cost;
int getcost(int x, int y){
if(cost.find({x, y}) == cost.end())
cost[{y, x}] = cost[{x, y}] = getDistance(x, y);
return cost[{x, y}];
}
struct Train{
int id;
int dist;
bool operator < (Train const &a) const{
return dist < a.dist;
}
};
std::map<int,char> type;
int mark[1 + nmax];
void findLocation(int N, int first, int location[], int stype[])
{
int pos = 1;
for(int i = 1;i < N; i++)
if(getcost(0, i) < getcost(0, pos))
pos = i;
location[0] = first;
stype[0] = 1;
type[location[0]] = 'C';
location[pos] = first + getcost(0, pos);
stype[pos] = 2;
type[location[pos]] = 'D';
std::vector<Train> v;
for(int i = 1; i < N; i++)
if(i != pos)
v.push_back({i, getcost(0, i)});
std::sort(v.begin(), v.end());
int last1 = 0, last2 = pos;
for(int i = 0; i < v.size(); i++){
int id = v[i].id;
if(getcost(0, pos) + getcost(pos, id) != getcost(0, id)){
int x = location[last2] - getcost(last2, id);
int y = (getcost(0, id) + x + location[0]) / 2;
if(getcost(0, id) == (2 * y - location[0] - x) && type[y] == 'D'){
location[id] = x;
stype[id] = 1;
type[location[id]] = 'C';
} else {
location[id] = location[0] + getcost(0, id);
stype[id] = 2;
type[location[id]] = 'D';
}
mark[id] = 1;
} else {
int x = location[last1] + getcost(last1, id);
int y = (x + location[pos] - getcost(pos, id)) / 2;
if(getcost(pos, id) == (x + location[pos] - 2 * y) && type[y] == 'C'){
location[id] = x;
stype[id] = 2;
type[location[id]] = 'D';
} else {
location[id] = location[pos] - getcost(pos, id);
stype[id] = 1;
type[location[id]] = 'C';
}
mark[id] = 2;
}
if(stype[id] == 2 && location[last2] < location[id])
last2 = id;
if(stype[id] == 1 && location[id] < location[last1])
last1 = id;
//std::cout << id << " " << location[id] << " " << stype[id] << '\n';
}
//std::cout << '\n';
//*
//std::cout << 0 << " " << location[0] << '\n';
//std::cout << pos << " " << location[pos] << '\n';
/*
for(int i = 0; i < N; i++)
out << stype[i] << " " << location[i] << " " << mark[i] << " " << getcost(0, i) << " " << getcost(pos, i) << '\n';
//*/
}
/*
1
5
1 1
1 2
2 6
2 7
2 8
*/
