e-maxx_algo

struct pt {

int x, y, id;

};

inline bool cmp_x (const pt & a, const pt & b) { return a.x < b.x || a.x == b.x && a.y < b.y;

}

inline bool cmp_y (const pt & a, const pt & b) { return a.y < b.y;

}

pt a[MAXN];

double mindist; int ansa, ansb;

inline void upd_ans (const pt & a, const pt & b) {

double dist = sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + .0); if (dist < mindist)

mindist = dist, ansa = a.id, ansb = b.id;

}

Наконец, реализация самой рекурсии. Предполагается, что перед её вызовом массив уже отсортирован по

-координате. Рекурсии передаётся просто два указателя , , которые указывают, что она должна искать ответ для . Если расстояние между и слишком мало, то рекурсию надо остановить, и выполнить

тривиальный алгоритм поиска ближайшей пары и затем отсортировать подмассив по -координате.

Для слияния двух множеств точек, полученных от рекурсивных вызовов, в одно (упорядоченное по -координате),

Наконец, множество хранится в том же массиве .

void rec (int l, int r) { if (r - l <= 3) {

for (int i=l; i<=r; ++i)

for (int j=i+1; j<=r; ++j) upd_ans (a[i], a[j]);

sort (a+l, a+r+1, &cmp_y); return;

}

int m = (l + r) >> 1; int midx = a[m].x;

rec (l, m), rec (m+1, r); static pt t[MAXN];

merge (a+l, a+m+1, a+m+1, a+r+1, t, &cmp_y); copy (t, t+r-l+1, a+l);

int tsz = 0;

for (int i=l; i<=r; ++i)

if (abs (a[i].x - midx) < mindist) {

for (int j=tsz-1; j>=0 && a[i].y - t[j].y < mindist;

--j)

upd_ans (a[i], t[j]); t[tsz++] = a[i];

}

}

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

В основной программе вызывать рекурсию следует так:

sort (a, a+n, &cmp_x); mindist = 1E20;

rec (0, n-1);

Обобщение: поиск треугольника с минимальным периметром

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

Задачи в online judges

Список задач, которые сводятся к поиску двух ближайших точек:

●CODEFORCES Командная олимпиада школьников Саратова - 2011 "Минимальная сумма" [сложность: средняя]

Преобразование геометрической инверсии

Преобразование геометрической инверсии (inversive geometry) — это особый тип преобразования точек на плоскости. Практическая польза этого преобразования в том, что зачастую оно позволяет свести решение геометрической задачи с окружностями к решению соответствующей задачи с прямыми, которая обычно имеет гораздо более простое решение.

По всей видимости, основоположником этого направления математики был Людвиг Иммануэль Магнус (Ludwig Immanuel Magnus), который в 1831 г. опубликовал статью об инверсных преобразованиях.

Определение

Зафиксируем окружность с центром в точке радиуса . Тогда инверсией точки относительно этой окружности называется такая точка , которая лежит на луче , а на расстояние наложено условие:

В терминах комплексных чисел преобразование инверсии выражается достаточно просто, если считать, что центр окружности совпадает с началом координат:

С помощью сопряжённого элемента можно получить более простую форму:

Применение инверсии (в точке-середине доски) к изображению шахматной доски даёт интересную картинку (справа):

Свойства

Очевидно, что любая точка, лежащая на окружности, относительно которой производится преобразование инверсии, при отображении переходит в себя же. Любая точка, лежащая внутри окружности,

переходит во внешнюю область, и наоборот. Считается, что центр окружности переходит в точку "бесконечность" , а точка "бесконечность" — наоборот, в центр окружности:

Очевидно, что повторное применение преобразования инверсии обращает первое её применение — все точки возвращаются обратно:

Обобщённые окружности

Обобщённая окружность — это либо окружность, либо прямая (считается, что это тоже окружность, но имеющая бесконечный радиус).

Ключевое свойство преобразования инверсии — что при его применении обобщённая окружность

всегда переходит в обобщённую окружность (подразумевается, что преобразование инверсии поточечно применяется ко всем точкам фигуры).

Сейчас мы увидим, что именно происходит с прямыми и окружностями при преобразовании инверсии.

Инверсия прямой, проходящей через точку

Утверждается, что любая прямая, проходящая через , после преобразования инверсии не меняется.

В самом деле, любая точка этой прямой, кроме и , переходит по определению тоже в точку этой прямой (причём в итоге получившиеся точки заполнят всю прямую целиком, поскольку преобразование инверсии обратимо). Остаются точки и , но при инверсии они переходят друг в друга, поэтому доказательство завершено.

Инверсия прямой, не проходящей через точку

Утверждается, что любая такая прямая перейдёт в окружность, проходящую через .

Рассмотрим любую точку этой прямой, и рассмотрим также точку — ближайшую к точку прямой. Понятно, что отрезок перпендикулярен прямой, а потому образуемый им угол — прямой.

Воспользуемся теперь леммой о равных углах, которую мы докажем чуть позже, эта лемма даёт нам равенство:

эту окружность целиком, следовательно, утверждение доказано.

Инверсия окружности, проходящей через точку

Любая такая окружность перейдёт в прямую, не проходящую через точку .

В самом деле, это сразу следует из предыдущего пункта, если мы вспомним об обратимости преобразования инверсии.

Инверсия окружности, не проходящей через точку

Любая такая окружность перейдёт в окружность, по-прежнему не проходящую через точку .

они разного знака).

При осуществлении последнего перехода мы изменили порядок следования точек, что и означает, что мы изменили ориентацию угла на противоположную.

Конформность

Преобразование инверсии является конформным, т.е. сохраняет углы в точках пересечения кривых. При этом, если углы рассматривать как ориентированные, то ориентация углов при применении инверсии изменяется на противоположную.

Для доказательства этого рассмотрим две произвольные кривые, пересекающиеся в точке и имеющие в ней касательные. Пусть по первой кривой будет идти точка , по второй — точка (мы их устремим в пределе к ).

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

Учитывая, что точка лежит на прямой, соединяющей и , получаем, что можем применить следствие из леммы о равных углах, из которой мы получаем:

где под знаком "минус" мы понимаем то, что углы ориентированы в разных направлениях.

Устремляя точки и к точке , мы в пределе получаем, что это равенство — выражение угла между пересекающимися кривыми, что и требовалось доказать.

Свойство отражения

Если — обобщённая окружность, то при преобразовании инверсии она сохраняется тогда и только тогда, когда ортогональна окружности , относительно которой производится инверсия ( и считаются различными).

Доказательство этого свойства интересно тем, что оно демонстрирует применение геометрической инверсии для ухода от окружностей и упрощения задачи.

Применение при решении задач вычислительной геометрии

Замечательное свойство геометрической инверсии — в том, что во многих случаях она позволяет упростить поставленную геометрическую задачу, заменяя рассмотрение окружностей только рассмотрением прямых.

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

Пример такой задачи описан в следующем разделе.

Цепочки Штейнера

Даны две окружности и , одна находится строго внутри другой. Затем рисуется третья окружность , касающаяся этих двух окружностей, после чего запускается итеративный процесс: каждый раз рисуется новая окружность так, чтобы она касалась предыдущей нарисованной, и первых двух. Рано или поздно очередная нарисованная окружность пересечётся с какой-то из уже поставленных, или по крайней мере коснётся её.

Случай пересечения:

Случай касания:

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

В случае касания получающая цепочка окружностей называется цепочкой Штейнера.

С этой цепочкой связано так называемое утверждение Штейнера (Steiner's porism): если существует хотя бы одна цепочка Штейнера (т.е. существует соответствующее положение стартовой касающейся окружности, приводящее к цепочке Штейнера), то при любом другом выборе стартовой касающейся окружности также будет получаться цепочка Штейнера, причём число окружностей в ней будет таким же.

Из этого утверждения следует, что и при решении задачи максимизации числа окружностей ответ не зависит от позиции первой поставленной окружности.

Доказательство и конструктивный алгоритм решения следующие. Заметим, что задача имеет очень