Пункт выдачи
Служба доставки открывает в городе пункт выдачи. Известны n мест, откуда приходят заказы: координаты (xi, yi) в метрах и число заказов wi из каждого места. Курьер возит каждый заказ отдельно, и для оценки путь считают по прямой. Найдите точку p, для которой суммарный путь
$$F(p) = \sum_{i=1}^{n} w_i \cdot \lvert p - a_i \rvert$$наименьший. Здесь ai = (xi, yi), а |…| — обычное расстояние на плоскости. Пункт можно поставить в любую точку, не обязательно на перекрёстке. Один из тестов — перекрёстки центра Алматы из OpenStreetMap с придуманным числом заказов.
Вход
В первой строке число мест n (1 ≤ n ≤ 10 000). В каждой из следующих n строк три целых числа xi, yi, wi (|xi|, |yi| ≤ 10⁶, 1 ≤ wi ≤ 10⁶). Места могут повторяться.
Выход
Два числа — координаты x и y пункта выдачи. Если подходящих точек несколько, выведите любую. Ответ засчитывается, если F в вашей точке больше наименьшего возможного не больше чем в 1 + 10⁻⁷ раз.
Примеры
Пример 1
4 0 0 1 400 0 1 400 300 1 0 300 1
200.000000 150.000000
Пример 2
3 0 0 5 1000 0 2 0 1000 2
0.000000 0.000000
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы курьер ездил не по прямой, а «по квадратам» — то есть надо было бы сделать наименьшей сумму wi·|p − ai|², — ответом был бы взвешенный центр масс. Почему здесь он не годится? Посмотрите на второй пример: куда должен встать пункт, если из одного места заказов больше, чем из всех остальных вместе?
2Подсказка 2
Формулы для ответа нет, но F — выпуклая функция, и у неё есть градиент везде, кроме самих точек ai: −∇F(p) = Σ wi·(ai − p)/|ai − p|. Каждое место тянет пункт к себе с силой wi, независимо от расстояния. Можно спускаться. Какой брать шаг?
3Подсказка 3
Приравняйте градиент нулю и выразите p: получится p = Σ(wi/di)·ai / Σ(wi/di), где di = |ai − p|. Правая часть зависит от p — подставляйте снова и снова.
4Идея
Это итерация Вейсфельда — её опубликовал в 1937 году математик Эндре Вейсфельд, позже сменивший фамилию и работавший в исследовании операций как Эндрю Вазсони. Новая точка — среднее мест с весами wi/di. Если расписать, это ровно шаг градиентного спуска p ← p − η∇F(p) с шагом η = 1/Σ(wi/di): шаг подбирается сам — короче, когда точка подошла близко к тяжёлым местам и функция там круто изгибается. Значение F на каждом шаге не растёт, и если ни один шаг не попадёт точно в одно из мест, итерации сходятся к минимуму.
Ловушка — сами места. В них градиента нет, и если ответ — одно из мест, итерации подползают к нему всё медленнее, а попав точно в него, делят на ноль. Для места aj есть точный признак: оно и есть ответ, когда остальные тянут его с суммарной силой не больше его собственного веса, |Σi≠j wi·(ai − aj)/|ai − aj|| ≤ wj. Во втором примере вес первого места 5, а остальные тянут его с силой 2√2 ≈ 2,83: пункт встаёт прямо в него.
5Разбор
Сначала сливаем одинаковые места, складывая их веса: так признак для места становится верным. Стартуем из центра масс и делаем шаги Вейсфельда, пока точка сдвигается больше чем на 10⁻⁷ метра (на тестах хватает нескольких десятков шагов). Если на каком-то шаге точка совпала с местом, проверяем признак: выполнен — ответ найден; нет — сдвигаемся с места на миллиметр в сторону, куда его тянут остальные, и продолжаем. В конце проверяем признак для ближайшего к итоговой точке места: если он выполнен, выводим само место — итерации к нему только подползали.
Сравните с центром масс. На перекрёстках центра Алматы он проигрывает минимуму всего несколько миллионных долей: облако точек почти симметрично, и обе точки рядом. В седьмом тесте тридцать далёких пригородов тянут центр масс к себе, и проигрыш уже около 0,3 %: в сумме квадратов далёкая точка весит непропорционально много, а в сумме расстояний — ровно столько, сколько в ней заказов.
5+Решение
6Сложность
O(n) на шаг, шагов обычно десятки; проверка признака — ещё O(n).
7Типичные ошибки
- Центр масс. Он делает наименьшей сумму квадратов расстояний, а не сумму расстояний. Во втором примере он в точке (2000/9; 2000/9), а ответ — в самом тяжёлом месте, (0; 0).
- Повторяющиеся места. Признак для места верен, только если одинаковые места слиты в одно с суммарным весом: иначе «другие» точки в той же позиции дают расстояние ноль.
- Постоянный шаг спуска. У функции излом в каждом месте, и спуск с постоянным шагом у ответа-места прыгает вокруг него, не попадая.
- Старт в центре масс без проверки. В десятом тесте центр масс попадает ровно в одно из мест, причём не в ответ: первый же шаг Вейсфельда делит на ноль.