Заметим, что если мы сдвинем все точки на какое-то расстояние — то матрица не изменитя. Тогда будем считать, что x1 = 0.
Найдем в матрице максимальное число — это расстояние между минимальной и максимальной точкой, пусть оно стоит в ячейке (i, j). Тогда мы можем взять любую из точек i, j как минимальную точку, вторая будет максимальной. От того, какая из точек будет минимальная существование ответа не зависит, а зависят лишь перестановки a и b.
Теперь найдем в i строке ноль — это будет расстояние между i-й точкой и точкой с таким же значением xi. Пусть этот ноль стоит в столбце k.
Теперь нужно найти перестановки a и b. Отсортируем i строку и по расстояниям. А также k столбец. Порядок точек в i строке даст перестановку b, а в j столбце — a. Одновременно с нахождением перестановок мы можем восстановить значения координат точек на прямой просто как расстояние от точки i, так как мы условились, что она находится в нуле.
Теперь остается не забыть проверить, что эти перестановки и координаты точек удовлетворяют данной матрице.