Автор задачи: Александр Гордеев, разработчик: Константин Бац
В задаче требовалось соединить три точки линиями так, чтобы линии шли по вертикалям или горизонталям клетчатой сетки и при этом имели минимальную суммарную длину.
Рассмотрим линию, которая в соответствии с условием соединяет две точки, например, первую и вторую. Длина такой линии — манхэттенское расстояние между двумя точкам, которое равно $$$|x_1 - x_2| + |y_1 - y_2|$$$. Заметим, что то же самое касается и кратчайших расстояний между остальными парами точек.
Давайте докажем, что итоговый ответ можно найти по формуле $$$d(i, j) = \max(x_i) - \min(x_i) + \max(y_i) - \min(y_i)$$$. К этому можно прийти двумя способами:
- Более интуитивный способ, который сложнее доказать — заметить, что так как любые две точки должны быть соединены, путь между точками $$$i$$$ и $$$j$$$ будет не короче $$$|x_i - x_j| + |y_i - y_j|$$$. При этом если мы проведем провода так, что они будут представлять три ломаных из трех наших точек в одну и ту же точку плоскости «между ними», то каждая эта ломаная войдет в два пути. Поэтому ответ равен $$$$$$0.5 \cdot (d(1, 2) + d(2, 3) + d(1, 3)) \text{,}$$$$$$ что, в свою очередь, равно полусумме $$$(\max -\ \mathrm{mid}) + (\mathrm{mid} - \min) + (\max - \min)$$$, то есть просто $$$\max - \min$$$ по каждой из координат.
- Либо можно было заметить, что нам понадобится минимум $$$\max x_i - \min x_i$$$ горизонтальных отрезков, чтобы соединить две наиболее удаленные по горизонтали точки, и то же самое по вертикали, поэтому меньшего ответа добиться нельзя. А пример с таким ответом строится достаточно тривиально (в зависимости от того, является ли «средняя» по $$$x$$$ точка минимальной или максимальной по $$$y$$$, или нет).