Возможен такой вариант решения задачи:

Используем бинарный поиск по ответу с заранее известным число итераций(допустим это будет 300). Левую границу времени установим на 0, а правую, например, на 2*Xmaxs. Каждый раз для момента времени m=(l+r)/2 будем проверять, верно ли, что скорость самого последнего участника к текущему моменту времени будет больше скорости первого(за линию). Если это так, то значит имеет смысл взять время большее, чем m, иначе меньшее. За 300 итераций мы явно добьемся достаточной точности.

Тогда по известному моменту времени мы легко сможем рассчитать расстояние от последнего до первого участника.

Таким образом, время работы программы O(log(Xmaxs)*N)