Путешествие из Ростова в Москву

Дядя Женя едет к дедушке Вове в гости из Ростова-на-Дону в Москву по трассе М-4. Миллионы россиян интересуются, к какому населенному пункту в данный момент ближе всего находится дядя Женя.

Реализуйте класс CityDetector, реализующий два метода:

constructor принимает points — массив объектов с информацией о расстоянии от начала трассы (km — номер километра и city — название населенного пункта)
detect принимает km — номер километра, где в данный момент находится дядя Женя, и возвращает название ближайшего населенного пункта.

Если два города находятся на одинаковом расстоянии от переданной позиции, то нужно вернуть ближайший к началу трассы.

Например, cd.detect(350) вернет "Новомосковск", т.к. на одинаковом расстоянии (20 км) находятся Новомосковск (330) и Елец (370), но Новомосковск ближе к Москве (330 < 370).

const points = [
  { km: 0, city: "Москва" },
  { km: 50, city: "Домодедово" },
  { km: 330, city: "Новомосковск" },
  { km: 370, city: "Елец" },
  { km: 460, city: "Липецк" },
  { km: 555, city: "Задонск" },
  { km: 620, city: "Воронеж" },
  { km: 920, city: "Каменск-Шахтинский" },
  { km: 1020, city: "Новочеркасск" },
  { km: 1060, city: "Ростов-на-Дону" },
  { km: 1400, city: "Краснодар" },
  { km: 1600, city: "Геленджик" },
  { km: 1670, city: "Новороссийск" }
];

const cd = new CityDetector(points);

console.log(cd.detect(50));   // "Домодедово"
console.log(cd.detect(1050)); // "Ростов-на-Дону"
console.log(cd.detect(694));  // "Воронеж"

Можно считать, что массив с городами отсортирован по номеру километра.

Предполагается, что трасса может быть длинной и содержать большое количество точек (т.к. вдоль трассы находятся не только населеные пункты), а интерес россиян может быть очень высоким.

Массив points содержит до 10 000 точек.
Метод detect вызывается до 10 000 000 раз.
Такое количество запросова должно обрабатываться в течение 1 секунды.

ЗадачаРедактор