#include "rail.h"
#include <cstdio>
//getDistance(i,j) --> distance from i to j
int d[3][5005];
int type[5005];
int pos[5005];
void findLocation(int n, int first, int location[], int stype[]){
int mnid = 0;
d[0][0] = 0x3f3f3f3f;
for (int i = 1; i < n; i++){
d[0][i] = getDistance(0, i);
if (d[0][i] < d[0][mnid]) mnid = i;
}
type[mnid] = 2;
int mnid2 = 0;
for (int i = 0; i < n; i++){
if (i == mnid) continue;
d[1][i] = getDistance(mnid, i);
if (d[1][i] < d[1][mnid2]) mnid2 = i;
}
for (int i = 0; i < n; i++){
if (i == mnid2) continue;
d[2][i] = getDistance(mnid2, i);
}
pos[mnid] = d[0][mnid] + first;
pos[mnid2] = pos[mnid] - d[1][mnid2];
type[mnid] = 2;
type[mnid2] = 1;
// printf("%d %d t%d\n", mnid, pos[mnid], type[mnid]);
// printf("%d %d t%d\n", mnid2, pos[mnid2], type[mnid2]);
for (int i = 0; i < n; i++){
if (i == mnid || i == mnid2) continue;
if (d[1][i] < d[2][i]){
type[i] = 1;
pos[i] = pos[mnid] - d[1][i];
} else {
type[i] = 2;
pos[i] = pos[mnid2] + d[2][i];
}
}
for (int i = 0; i < n; i++){
location[i] = pos[i];
stype[i] = type[i];
}
}
