Алгоритмы C++

Теорема Пика. Нахождение площади решётчатого многоугольника

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

Теорема Пика

Пусть дан некоторый решётчатый многоугольник. Обозначим его площадь через S; количество точек с целочисленными координатами, лежащих строго внутри многоугольника - через I; количество точек с целочисленными координатами, лежащих на сторонах многоугольника - через B. Тогда справедливо соотношение:

S = I + B/2 - 1

В частности, если известны значения I и B для некоторого многоугольника, то его площадь можно посчитать за O (1). Это соотношение было открыто и доказано Пиком (Pick) в 1899 г.

Задача о покрытии отрезков точками

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

Также рассмотрим усложнённый вариант этой задачи - когда дополнительно указано "запрещённое" множество отрезков, т.е. никакая точка из ответа не должна принадлежать ни одному запрещённому отрезку.

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

Ниже будет описан жадный алгоритм, решающий обе задачи за O (N log N).

Решение первой задачи

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

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

Однако при наивной реализации этот метод будет работать за O (N2). Опишем эффективную реализацию этого метода.

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

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

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

Таким образом, весь алгоритм выполняется за O (N), не считая сортировки точек, а итоговая сложность алгоритма как раз равна O (N log N).

Решение второй задачи

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

Снова возьмём все точки-концы отрезков (как целевых отрезков, так и запрещённых), отсортируем их, сохранив вместе с каждой точкой её тип и отрезок, концом которого она является. Опять же, отсортируем отрезки так, чтобы при равенстве координат левые концы шли перед правыми, а если и типы концов равны, то левые концы запрещённых должны идти перед левыми концами целевых, а правые концы запрещённых - после целевых (чтобы запрещённые отрезки учитывались как можно дольше при равенстве координат). Заведём счётчик запрещённых отрезков, который будет равен числу запрещённых отрезков, покрывающих текущую точку. Заведём очередь (queue), в которой будут храниться номера текущих целевых отрезков. Будем перебирать точки

вотсортированном порядке. Если текущая точка - левый конец целевого отрезка, то просто добавим номер её отрезка

вочередь. Если текущая точка - правый конец целевого отрезка, то, если счётчик запрещённых отрезков равен нулю, то мы поступаем аналогично предыдущей задаче - ставим точку в текущую точку, и выталкиваем все отрезки из очереди, отмечая, что они покрыты. Если же счётчик запрещённых отрезков больше нуля, то в текущую точку мы стрелять не можем, а потому мы должны найти самую последнюю точку, свободную от запрещённых отрезков; для этого надо поддерживать соответствующий указатель last_free, который будет обновляться при поступлении запрещённых отрезков. Тогда мы стреляем в last_free-EPS (потому что прямо в неё нельзя стрелять - эта

точка принадлежит запрещённому отрезку), и выталкивать отрезки из очереди, пока точка last_free-EPS принадлежит им. А именно, если текущая точка - левый конец запрещённого отрезка, то мы увеличиваем счётчик, и если перед этим счётчик был равен нулю, то присваиваем last_free текущую координату. Если текущая точка - правый конец запрещённого отрезка, то просто уменьшаем счётчик.

Пересечение окружности и прямой

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

Решение

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

Предположим, не теряя общности, что центр окружности находится в начале координат (если это не так, то перенесём его туда, исправив соответствующе константу C в уравнении прямой). Т.е. имеем окружность с центром в (0,0) радиуса r и прямую с уравнением Ax + By + C = 0.

Сначала найдём ближайшую к центру точку прямой - точку с некоторыми координатами (x0,y0). Во-первых, эта точка должна находиться на таком расстоянии от начала координат:

|C|

----------

sqrt(A2+B2)

Во-вторых, поскольку вектор (A,B) перпендикулярен прямой, то координаты этой точки должны быть пропорциональны координатам этого вектора. Учитывая, что расстояние от начала координат до искомой точки нам известно, нам нужно просто нормировать вектор (A,B) к этой длине, и мы получаем:

A C x0 = - -----

A2+B2

B C y0 = - -----

A2+B2

(здесь неочевидны только знаки 'минус', но эти формулы легко проверить подстановкой в уравнение прямой - должен получиться ноль)

Зная ближайшую к центру окружности точку, мы уже можем определить, сколько точек будет содержать ответ, и даже дать ответ, если этих точек 0 или 1.

Действительно, если расстояние от (x0, y0) до начала координат (а его мы уже выразили формулой - см. выше)

больше радиуса, то ответ - ноль точек. Если это расстояние равно радиусу, то ответом будет одна точка - (x0,y0). А вот в оставшемся случае точек будет две, и их координаты нам предстоит найти.

Итак, мы знаем, что точка (x0, y0) лежит внутри круга. Искомые точки (ax,ay) и (bx,by), помимо того что должны принадлежать прямой, должны лежать на одном и том же расстоянии d от точки (x0, y0), причём это расстояние легко найти:

C2

d = sqrt ( r2 - ----- ) A2+B2

Заметим, что вектор (-B,A) коллинеарен прямой, а потому искомые точки (ax,ay) и (bx,by) можно получить, прибавив к точке (x0,y0) вектор (-B,A), нормированный к длине d (мы получим одну искомую точку), и вычтя этот же вектор

(получим вторую искомую точку). Окончательное решение такое:

d2 mult = sqrt ( ----- )

A2+B2

ax = x0 + B mult ay = y0 - A mult bx = x0 - B mult by = y0 + A mult

Если бы мы решали эту задачу чисто алгебраически, то скорее всего получили бы решение в другом виде, которое даёт бОльшую погрешность. Поэтому "геометрический" метод, описанный здесь, помимо наглядности, ещё и более точен.

Реализация

Как и было указано в начале описания, предполагается, что окружность расположена в начале координат. Поэтому входные параметры - это радиус окружности и коэффициенты A,B,C уравнения прямой.

double r, a, b, c; // входные данные

double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b); if (c*c > r*r*(a*a+b*b)+EPS)

puts ("no points");

else if (abs (c*c - r*r*(a*a+b*b)) < EPS) { puts ("1 point");

cout << x0 << ' ' << y0 << '\n';

}

else {

double d = r*r - c*c/(a*a+b*b); double mult = sqrt (d / (a*a+b*b)); double ax,ay,bx,by;

ax = x0 + b * mult; bx = x0 - b * mult; ay = y0 - a * mult; by = y0 + a * mult; puts ("2 points");

cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';

}

Пересечение двух окружностей

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

Решение

Сведём нашу задачу к задаче о Пересечении окружности и прямой.

Предположим, не теряя общности, что центр первой окружности - в начале координат (если это не так, то перенесём центр в начало координат, а при выводе ответа будем обратно прибавлять координаты центра). Тогда мы имеем систему двух уравнений:

x2 + y2 = r12

(x - x2)2 + (y - y2)2 = r22

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

x2 + y2 = r12

x (-2x2) + y (-2y2) + (x22 + y22 + r12 - r22) = 0

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

Ax + By + C = 0,

A = -2x2,

B = -2y2,

C = x22 + y22 + r12 - r22.

А решение последней задачи описано в соответствующей статье.

Единственный вырожденный случай, который надо рассмотреть отдельно - когда центры окружностей совпадают. Действительно, в этом случае вместо уравнения прямой мы получим уравнение вида 0 = С, где C - некоторое число, и этот случай будет обрабатываться некорректно. Поэтому этот случай нужно рассмотреть отдельно: если радиусы окружностей совпадают, то ответ - бесконечность, иначе - точек пересечения нет.

Построение выпуклой оболочки обходом Грэхэма

Даны N точек на плоскости. Построить их выпуклую оболочку, т.е. наименьший выпуклый многоугольник, содержащий все эти точки.

Мы рассмотрим метод Грэхэма (Graham) (предложен в 1972 г.) с улучшениями Эндрю (Andrew) (1979 г.). С его помощью можно построить выпуклую оболочку за время O (N log N) с использованием только операций сравнения, сложения и умножения. Алгоритм является асимптотически оптимальным (доказано, что не существует алгоритма с лучшей асимптотикой), хотя в некоторых задачах он неприемлим (в случае параллельной обработки или при online-обработке).

Описание

Алгоритм. Найдём самую левую и самую правую точки A и B (если таких точек несколько, то возьмём самую нижнюю среди левых, и самую верхнюю среди правых). Понятно, что и A, и B обязательно попадут в выпуклую оболочку. Далее, проведём через них прямую AB, разделив множество всех точек на верхнее и нижнее подмножества S1 и S2 (точки, лежащие на прямой, можно отнести к любому множеству - они всё равно не войдут в оболочку). Точки A и

B отнесём к обоим множествам. Теперь построим для S1 верхнюю оболочку, а для S2 - нижнюю оболочку, и объединим их, получив ответ. Чтобы получить, скажем, верхнюю оболочку, нужно отсортировать все точки по абсциссе, затем пройтись по всем точкам, рассматривая на каждом шаге кроме самой точки две предыдущие точки, вошедшие в оболочку. Если текущая тройка точек образует не правый поворот (что легко проверить с помощью Ориентированной площади), то ближайшего соседа нужно удалить из оболочки. В конце концов, останутся только

точки, входящие в выпуклую оболочку.

Итак, алгоритм заключается в сортировке всех точек по абсциссе и двух (в худшем случае) обходах всех точек, т. е. требуемая асимптотика O (N log N) достигнута.

Реализация

struct pt {

double x, y;

};

bool cmp (pt a, pt b) {

return a.x < b.x || a.x == b.x && a.y < b.y;

}

bool cw (pt a, pt b, pt c) {

return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;

}

bool ccw (pt a, pt b, pt c) {

return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;

}

void convex_hull (vector<pt> & a) { if (a.size() == 1) return;

sort (a.begin(), a.end(), &cmp); pt p1 = a[0], p2 = a.back(); vector<pt> up, down; up.push_back (p1); down.push_back (p1);

for (size_t i=1; i<a.size(); ++i) {

if (i==a.size()-1 || cw (p1, a[i], p2)) {

while (up.size()>=2 && !cw (up[up.size()-2], up[up.

size()-1], a[i]))

up.pop_back(); up.push_back (a[i]);

}

if (i==a.size()-1 || ccw (p1, a[i], p2)) {

while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))

down.pop_back(); down.push_back (a[i]);

}

}

a.clear();

for (size_t i=0; i<up.size(); ++i) a.push_back (up[i]);

for (size_t i=down.size()-2; i>0; --i) a.push_back (down[i]);

}