Тема: Сумма Минковского
Недавно узнал про эту интересную штуку. Писать статью всё равно не буду (кода нет, да и времени нет), поэтому здесь.
Сумма Минковского для двух геометрических фигур - это фигура, составленная из всевозможных точек вида a+b, где точка a принадлежит первой фигуре, b - второй. Понятно, что сумму можно применять вообще к любым двум множествам.
Интересно то, что эту сумму можно вычислять даже за линейное время, если входные многоугольники - выпуклые. Как - не знаю, предлагаю читателям подумать Эта задача, оказывается, даже была достаточно много лет назад на IOI
А интереснее всего то, что эту на первый взгляд абстрактную штуку можно вполне практично применять: оказывается, так можно получить критерий пересечения многоугольников. Действительно, если сумма Минковского содержит точку (0,0), то первый многоугольник содержит точку (x,y), а второй - (-x,-y). Стало быть, если у одного из них изначально поменять знак всех координат, то точка (0,0) в сумме Минковского сигнализирует о том, что многоугольники имеют общую точку.
Более того, если сдвинуть один многоугольник на некоторый вектор, то и сумма сдвинется на тот же вектор. Таким образом, мы сразу получаем решение такой задачи: найти вектор (и даже множество всех таких векторов!), что при сдвиге одного многоугольника он только лишь касается другого.