Сборы | Т-банк & Сборник Олпрогера

Сборы | Т-банк & Сборник Олпрогера

Разбор пятого тура.pdf

Альтернативное решение последней задачи с разбора:

Повернем плоскость на 45 градусов преобразованием (x, y) →(x−y, x + y). Тогда расстояние между двумя точками это max(|x′_1−x′_2|, |y′_1−y′_2|). Воспользуемся двоичным поиском по искомому расстоянию, будем проверять, есть ли k пар точек с расстоянием, не превосходящим x. В новой метрике, для некоторой точки, все подходящие точки должны лежать в квадрате со стороной x. Будем перебирать точку i и для неё находить все точки, лежащие слева от нее в квадрате, со стороной x. Будем поддерживать в множестве все точки, которые находятся на расстоянии не большем d по координате x, и хранить эти точки отсортированными по их y. Тогда найти эти точки можно используя lower_bound, затем последовательно по ним пройдясь (суммарно пройдем не более k точек на каждой итерации бинпоиска). Для восстановления ответа восстановим все расстояния, для расстояния min−1, остальные будут иметь расстояние min.

www.tgoop.com/t_sbory/145

2.7K viewsJan 8 at 15:36

Альтернативное решение последней задачи с разбора:

Повернем плоскость на 45 градусов преобразованием (x, y) →(x−y, x + y). Тогда расстояние между двумя точками это max(|x′_1−x′_2|, |y′_1−y′_2|). Воспользуемся двоичным поиском по искомому расстоянию, будем проверять, есть ли k пар точек с расстоянием, не превосходящим x. В новой метрике, для некоторой точки, все подходящие точки должны лежать в квадрате со стороной x. Будем перебирать точку i и для неё находить все точки, лежащие слева от нее в квадрате, со стороной x. Будем поддерживать в множестве все точки, которые находятся на расстоянии не большем d по координате x, и хранить эти точки отсортированными по их y. Тогда найти эти точки можно используя lower_bound, затем последовательно по ним пройдясь (суммарно пройдем не более k точек на каждой итерации бинпоиска). Для восстановления ответа восстановим все расстояния, для расстояния min−1, остальные будут иметь расстояние min.

BY Сборы | Т-банк & Сборник Олпрогера