#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
const int TAILLE_MAX=5000+5,INFINI=1000*1000*1000;
int nbBloc;
int dist[TAILLE_MAX][TAILLE_MAX];
void findLocation(int N, int first, int location[], int stype[]) {
nbBloc=N;
location[0]=first;
stype[0]=1;
if (N==1) {
return ;
}
for (int i=0;i<nbBloc;i++) {
for (int j=i+1;j<nbBloc;j++) {
dist[i][j]=getDistance(i,j);
dist[j][i]=dist[i][j];
}
}
vector<pair<int,int>> somTri;
vector<int> listeD;
int pos,pb;
for (int i=1;i<nbBloc;i++) {
somTri.push_back({dist[0][i],i});
}
sort(somTri.begin(),somTri.end());
for (auto i:somTri) {
pos=i.second;
pb=0;
for (int j:listeD) {
if (dist[0][pos]==dist[0][j]+dist[j][pos]) {
pb=1;
}
}
if (pb==0) {
listeD.push_back(pos);
}
}
int dernD=listeD.back();
vector<int> listeC;
location[dernD]=first+dist[0][dernD];
stype[dernD]=2;
somTri.clear();
for (int i=0;i<nbBloc;i++) {
if (i!=dernD) {
somTri.push_back({dist[dernD][i],i});
}
}
sort(somTri.begin(),somTri.end());
for (auto i:somTri) {
pos=i.second;
pb=0;
for (int j:listeC) {
if (dist[dernD][pos]==dist[dernD][j]+dist[j][pos]) {
pb=1;
}
}
if (pb==0) {
listeC.push_back(pos);
location[pos]=location[dernD]-dist[dernD][pos];
stype[pos]=1;
}
}
int dernC=listeC.back();
listeD.clear();
somTri.clear();
for (int i=0;i<nbBloc;i++) {
if (i!=dernC) {
somTri.push_back({dist[dernC][i],i});
}
}
sort(somTri.begin(),somTri.end());
for (auto i:somTri) {
pos=i.second;
pb=0;
for (int j:listeD) {
if (dist[dernC][pos]==dist[dernC][j]+dist[j][pos]) {
pb=1;
}
}
if (pb==0) {
listeD.push_back(pos);
location[pos]=location[dernC]+dist[dernC][pos];
stype[pos]=2;
}
}
return;
}
