анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 19 из 26

Глава
13
Геометрия
В этой главе обсуждаются алгоритмы, относящиеся к геометрии. Наша цель – найти способы, позволяющие удобно решать геометрические зада- чи, избегая особых случаев и корявых реализаций.
В разделе 13.1 мы познакомимся с классом комплексных чисел из стан- дартной библиотеки C++, в котором имеются полезные средства для ре- шения геометрических задач. Затем мы узнаем о применении векторного произведения для решения таких задач, как проверка пересечения двух отрезков и вычисление расстояния от точки до прямой. Наконец, мы обсу- дим различные способы вычисления площади многоугольников и специ- альные свойства манхэттенского расстояния.
Раздел 13.2 посвящен алгоритмам на основе заметающей прямой, ко- торые играют важную роль в вычислительной геометрии. Мы увидим, как такие алгоритмы используются для подсчета точек пересечения, нахожде- ния ближайших точек и построения выпуклой оболочки.
13.1. Технические средства в геометрии
При решении геометрических задач возникает общая проблема: найти подход, позволяющий свести количество особых случаев к минимуму, и придумать удобный способ реализации решения. В этом разделе мы рас- смотрим ряд инструментов, упрощающих решение геометрических задач.
13.1.1. Комплексные числа
Комплексное число имеет вид x + yi, где i = √–1
– так называемая мнимая
единица. Геометрически комплексное число интерпретируется как точка на двумерной плоскости (x, y)или как вектор, соединяющий начало ко- ординат с точкой (x, y). На рис. 13.1 изображено комплексное число 4 + 2i.
В стандартной библиотеке C++ имеется класс complex для представления комплексных чисел, он полезен при решении геометрических задач. С по- мощью этого класса мы можем представлять точки и векторы как комп- лексные числа и использовать методы класса для операций над этими объектами. Для этого сначала определим тип координат C. В зависимости от ситуации это может быть тип long long или long double
. Вообще го-

248 
Глава 13. Геометрия воря, лучше по возможности работать с целочисленными координатами, поскольку вычисления в этом случае точны.
(4, 2)
Рис. 13.1. Комплексное число 4 + 2i, интерпретируемое как точка и как вектор
Вот возможные определения типа координат:
typedef long long C;
typedef long double C;
Затем определим тип комплексного числа
P
, представляющий точку или вектор:
typedef complex P;
Наконец, определим макросы для ссылки на координаты x и y:
#define X real()
#define Y imag()
Например, в следующем фрагменте создается точка p = (4, 2) и печата- ются ее координаты x и y:
P p = {4,2};
cout << p.X << "" << p.Y << "\n"; // 4 2
А ниже создаются векторы v = (3, 1)и u = (2, 2), после чего вычисляется их сумма s = v + u.
P v = {3,1};
P u = {2,2};
P s = v+u;
cout << s.X << "" << s.Y << "\n"; // 5 3
Функции. В классе complex имеются также функции, полезные для ре- шения геометрических задач. Описанные ниже функции следует исполь- зовать, только когда тип координат long double
(или другой тип с плаваю- щей точкой).

13.1. Технические средства в геометрии

249
Функция abs
(v)вычисляет длину |v| вектора v = (x, y)по формуле √x
2
+
y
2
Ее можно также использовать для вычисления расстояния между точка- ми (x
1
, y
1
)и (x
2
, y
2
), поскольку это расстояние равно длине вектора (x
2
– x
1
,
y
2
– y
1
). В следующем коде вычисляется расстояние между точками (4, 2) и
(3, −1).
P a = {4,2};
P b = {3,-1};
cout << abs(b-a) << "\n"; // 3.16228
Функция arg
(v)вычисляет полярный угол между вектором v = (x, y)и поло- жительным направлением оси x, т. е. для вектора, направленного вправо, угол равен нулю и возрастает против часовой стрелки. Функция возвраща- ет угол в радианах (r радиан равно 180r/π градусов).
Функция polar
(s, a) конструирует вектор длины s, наклоненный к оси x под углом a, выраженным в радианах. Для поворота вектора на угол a его нужно умножить на вектор длины 1 с полярным углом a.
В следующем коде вычисляется полярный угол вектора (4, 2), затем век- тор поворачивается на 1/2 радиана, и снова вычисляется полярный угол:
P v = {4,2};
cout << arg(v) << "\n"; // 0.463648
v *= polar(1.0,0.5);
cout << arg(v) << "\n"; // 0.963648
13.1.2. Точки и прямые
Векторное произведение a × b векторов a = (x
1
, y
1
)и b = (x
2
, y
2
)определяется как x
1
y
2
− x
2
y
1
. Оно дает направление вектора b относительно вектора a. На рис. 13.2 показаны три возможных случая:
• a × b > 0: b повернут относительно a влево;
• a × b = 0: направления a и b совпадают или противоположны;
• a × b < 0: b повернут относительно a вправо.
a b
a × b > 0
a b
a × b = 0
a b
a × b < 0
Рис. 13.2. Интерпретация векторного произведения

250 
Глава 13. Геометрия
Например, векторное произведение векторов a = (4, 2) и b = (1, 2) равно
4 · 2 – 2 · 1 = 6, что соответствует первому случаю на рис. 13.2. Ниже пока- зано, как вычисляется векторное произведение:
P a = {4,2};
P b = {1,2};
C p = (conj(a)*b).Y; // 6
Этот код работает, потому что функция conj меняет знак координаты
y
вектора, а координата y произведения векторов (x
1
, −y
1
)и (x
2
, y
2
)равна
x
1
y
2
− x
2
y
1
Рассмотрим некоторые применения векторного произведения.
Проверка положения точки относительно
прямой. Векторное произведение позволяет узнать, как расположена точка относительно прямой: слева или справа. Предположим, что прямая проходит через точки s
1
и s
2
, что мы смотрим из s
1
в s
2
и что дана точка p. Так, на рис. 13.3 точка p расположена слева от прямой.
Положение точки p можно узнать, вычислив векторное произведение (p − s
1
) × (p − s
2
). Если оно положительно, то p расположена слева от прямой, если отрицательно, то справа, а если равно нулю, то точки s
1
, s
2
и p лежат на одной прямой.
Пересечение отрезков. Предположим теперь, что требуется узнать, пе- ресекаются ли два отрезка ab и cd. Если отрезки пересекаются, то возмож- ны три случая.
Случай 1. Отрезки лежат на одной прямой и частично перекрываются. В этом случае количество точек пересечения бесконечно.
Так, на рис. 13.4 все точки между c и b яв- ляются точками пересечения. Чтобы рас- познать этот случай, можно воспользовать- ся векторным произведением и проверить, лежат ли все четыре точки на одной пря- мой. Если да, то отсортируем их и проверим, пере крываются ли отрезки.
Случай 2.Отрезки имеют общий конец, ко- торый является единственной точкой пере- сечения. На рис. 13.5
точкой пересечения является b = c. Этот случай легко проверить, т. к. всего существует четыре возможные точки пересечения: a = c, a = d, b = c и b = d.
s
1
s
2
p
Рис. 13.3. Проверка положения точки относительно прямой a
d c
b
Рис. 13.4. Случай 1: отрезки лежат на одной прямой и перекрываются a
b
= c d
Рис. 13.5. Случай 2: отрезки имеют общий конец

13.1. Технические средства в геометрии

251
Случай 3. Существует одна точка пересече- ния, не являющаяся общим концом отрезков.
На рис. 13.6 p – точка пересечения. В этом случае отрезки пересекаются тогда и только тогда, когда точки c и d лежат по разные сто- роны от прямой, проходящей через a и b, а точки a и b – по разные стороны от прямой, проходящей через c и d. Это можно прове- рить, вычислив векторные произведения.
Расстояние от точки до прямой. Еще одно свойство векторного произведения со- стоит в том, что площадь треугольника мож- но вычислить по формуле
|(a − c) × (b − c)| ,
2
где a, b и c – вершины треугольника. Зная это, мы можем вывести формулу для вы- числения кратчайшего расстояния меж- ду точкой и прямой. На рис. 13.7 буквой d
обозначено кратчайшее расстояние между точкой p и прямой, проходящей через точ- ки s
1
и s
2
Площадь треугольника с вершинами s
1
,
s
2
и p можно вычислить двумя способами:
1 2
|s
2
− s
1
|d (стандартная школь- ная формула) и
1 2
((s
1
− p)× (s
2
− p))(формула с применением векторного произведения). Следовательно, кратчайшее расстояние равно
1 2
2 1
(
) (
)
s
p
s
p
d
s
s
−
×
−
=
−
Точка внутри многоугольника. Наконец, обсудим, как узнать, нахо- дится ли точка внутри или вне многоугольника. На рис. 13.8 точка a нахо- дится внутри, а точка b – вне многоугольника.
Для решения этой задачи удобно провести луч из точки в произвольном направлении и посчитать, сколько раз он пересекает границу многоуголь- ника. Если это число нечетное, то точка находится внутри, а если четное, то вне.
Так, на рис. 13.9 лучи, проведенные из точки a, пересекают границу многоугольника 1 и 3 раза, поэтому a находится внутри. Аналогично лучи, проведенные из точки b,пересекают границу 0 и 2 раза, поэтому b нахо- дится вне многоугольника.
c d
a b
p
Рис. 13.6. Случай 3: отрезки пересекаются в точке, не являющейся концом s
1
s
2
p d
Рис. 13.7. Вычисление расстояния от точки p до прямой

252 
Глава 13. Геометрия a
b
Рис. 13.8. Точка a находится внутри многоугольника, а точка b вне его a
b
Рис. 13.9. Проведение лучей из точек a и b
13.1.3. Площадь многоугольника
Общая формула вычисления площади многоугольника иногда называ- ется формулой шнурования:
1 1
1 1
1 1
1 1
1
(
)
(
) .
2 2
n
n
i
i
i
i
i
i
i
i
p
p
x y
x
y
−
−
+
+
+
=
=
×
=
−
∑
∑
Здесь вершины многоугольника p
1
= (x
1
, y
1
), p
2
= (x
2
, y
2
), …, p
n
= (x
n
, y
n
)
упорядочены таким образом, что p
i
и p
i
+1
– соседние вершины, а первая вершина совпадает с последней, т. е. p
1
= p
n
(4, 1)
(7, 3)
(5, 5)
(2, 4)
(4, 3)
Рис. 13.10. Многоугольник площади 17/2

13.1. Технические средства в геометрии

253
Например, площадь многоугольника на рис. 13.10 равна
|(2 · 5 − 5 · 4) + (5 · 3 − 7 · 5) + (7 · 1 − 4 · 3) + (4 · 3 − 4 · 1) + (4 · 4 − 2 · 3)| = 17/2.
2
Для вывода этой формулы многоугольник покрывается трапециями, одна сторона которых совпадает со стороной многоугольника, а другая лежит на горизонтальной оси y = 0. На рис. 13.11 показана одна такая трапеция.
(4,1)
(7,3)
(5,5)
(2,4)
(4,3)
Рис. 13.11. Вычисление площади многоугольника методом трапеций
Площадь каждой трапеции равна
1 1
(
)
,
2
i
i
i
i
y
y
x
x
+
+
+
−
где (x
i
, y
i
) и (x
i
+1
, y
i
+1
) – координаты вершин p
i
и p
i
+1
многоугольника. Если
x
i
+1
> x
i
, то площадь положительна, а если x
i
+1
< x
i
, то отрицательная. Про- суммировав площади всех трапеций, получим формулу площади много- угольника:
1 1
1 1
1 1
1 1
1
(
)
(
) .
2 2
n
n
i
i
i
i
i
i
i
i
i
i
y
y
x
x
x y
x
y
−
−
+
+
+
+
=
=
+
−
=
−
∑
∑
Мы берем абсолютную величину, потому что сумма может оказаться положительной или отрицательной в зависимости от направления обхода границы многоугольника.
Теорема Пика дает еще один способ вычисления площади много- угольника, все вершины которого имеют целочисленные координаты. Она утверждает, что площадь равна
a + b/2 − 1,
где a – количество целых точек внутри многоугольника, а b – количест- во целых точек на его границе. Например, площадь многоугольника на рис. 13.12 равна
6 + 7/2 − 1 = 17/2.

254 
Глава 13. Геометрия
(4,1)
(7,3)
(5,5)
(2,4)
(4,3)
Рис. 13.12. Вычисление площади многоугольника с помощью теоремы Пика
13.1.4. Метрики
Метрика определяет расстояние между двумя точками. Обычное евкли-
дово расстояние между точками (x
1
, y
1
)и (x
2
, y
2
) равно
2 2
2 1
2 1
)
(
)
(
+
x
x
y
y
−
−
Манхэттенское расстояние между точками (x
1
, y
1
)и (x
2
, y
2
) вычисляется по формуле
|x
1
− x
2
| + |y
1
– y
2
|.
На рис. 13.13 евклидово расстояние между точками равно
2 2
5
)
(2 1 10
)
(
2 +
=
−
−
,
а манхэттенское расстояние между ними же равно
|5 − 2| + |2 − 1| = 4.
(2, 1)
(5, 2)
(2, 1)
(5, 2)
Manhattan distance
Euclidean distance
Евклидово расстояние Манхэттенское расстояние
Рис. 13.13. Две метрики
На рис. 13.14 показано, как выглядят единичные круги – множества то- чек, удаленных от центра на расстояние, не большее 1, – при использова- нии евклидовой и манхэттенской метрик.

13.1. Технические средства в геометрии

255
Euclidean distance
Manhattan distance
Евклидово расстояние Манхэттенское расстояние
Рис. 13.14. Единичные круги
Некоторые задачи проще решить, если использо- вать манхэттенское, а не евклидово расстояние. На- пример, пусть дано множество точек на плоскости и требуется найти пару точек, для которых манхэттен- ское расстояние максимально. Так, на рис. 13.15 ман- хэттенское расстояние между точками B и C макси- мально и равно 5.
При работе с манхэттенским расстоянием быва- ет полезно применить преобразование координат
(x, y)→ (x + y, y − x). При этом происходят поворот на
45° и масштабирование. На рис. 13.16 показан резуль- тат этого преобразования в нашем примере.
Рассмотрим теперь две точки p
1
= (x
1
, y
1
)и p
2
= (x
2
, y
2
), которые после пре- образования перешли в p'
1
= (x'
1
, y'
1
)и p'
2
= (x'
2
, y'
2
). Манхэттенское расстояние между p
1
и p
2
можно выразить двумя способами:
|x
1
– x
2
| + |y
1
– y
2
| = max(|x'
1
– x'
2
|, |y'
1
– y'
2
|).
Например, если p
1
= (1, 0) и p
2
= (3, 3), то пре- образованные координаты равны p'
1
= (1, −1) и
p'
2
= (6, 0), а манхэттенское расстояние
|1 − 3| + |0 − 3| = max(|1 − 6|, |−1 − 0|) = 5.
Преобразование координат дает простой спо- соб работать с манхэттенскими расстояниями, потому что координаты x и y можно рассматри- вать порознь. В частности, чтобы максимизи- ровать манхэттенское расстояние, необходимо найти такие две точки, что их преобразованные координаты доставляют максимум величине max(|x'
1
– x'
2
|, |y'
1
– y'
2
|).
Это легко, потому что должна быть максимальна разность горизонталь- ных или вертикальных координат после преобразования.
A
C
B
D
Рис. 13.15. Манхэт- тенское расстояние между точками B и C максимально
A
C
B
D
Рис. 13.16. Максималь- ное манхэттенское расстояние после преоб- разования координат

256 
Глава 13. Геометрия
13.2. Алгоритмы на основе заметающей прямой
Многие геометрические задачи можно решить с помощью заметающей прямой. Идея в том, чтобы представить задачу в виде множества событий, соответствующих точкам на плоскости. Затем события обрабатываются в порядке возрастания координаты x или y.
13.2.1. Точки пересечения
Дано множество n горизонтальных и вертикальных отрезков, требуется вычислить количество точек их пересечения. На рис. 13.17 показаны пять отрезков и три точки пересечения.
Рис. 13.17. Пять отрезков, пересекающихся в трех точках
Задачу легко решить за время O(n
2
), перебрав все пары отрезков и про- верив, пересекаются они или нет. Но можно ограничиться временем O(n
log n), если воспользоваться заметающей прямой и структурой данных для запроса по диапазону. Идея в том, чтобы просматривать концевые точки отрезков слева направо, обрабатывая следующие события:
(1) горизонтальный отрезок начался;
(2) горизонтальный отрезок закончился;
(3) встретился вертикальный отрезок.
На рис. 13.18 показаны эти события в нашем примере.
1 2
1 2
1 2
3 3
Рис. 13.18. События, соответствующие отрезкам
Создав события, мы пробегаем по ним слева направо, используя струк- туру данных, в которой хранятся координаты y активных горизонтальных

13.2. Алгоритмы на основе заметающей прямой

257
отрезков. При обработке события 1 координата y отрезка добавляется в структуру, а при обработке события 2 удаляется из нее. При обработке со- бытия 3 вычисляются точки пересечения: если координаты концов верти- кального отрезка равны y
1
и y
2
, то мы подсчитываем количество активных горизонтальных отрезков, для которых координата y лежит между y
1
и y
2
, и прибавляем это число к общему числу точек пересечения.
Для хранения координат y горизонтальных отрезков можно использо- вать двоичное индексное дерево или дерево отрезков, возможно, со сжа- тием индексов. Обработка одного события занимает время O(log n), так что временная сложность алгоритма равна O(n log n).
13.2.2. Задача о ближайшей паре точек
Далее рассмотрим такую задачу: дано множество n точек, требуется найти две точки, евклидово расстояние между которыми наименьшее. На рис. 13.19 изображено множество точек, а ближайшая пара выделена чер- ным.
Рис. 13.19. Пример задачи о ближайшей паре точек
Это еще один пример задачи, которую можно решить за время O(n log n)
с помощью алгоритма на основе заметающей прямой
1
. Мы просматрива- ем точки слева направо и храним значение d: минимальное расстояние между двумя встретившимися до сих пор точками. Если расстояние мень- ше d, то оно становится новым минимальным расстоянием и значение d обновляется.
Если (x, y)– текущая точка и слева от нее существует точка, удаленная на расстояние меньше d, то координата x такой точки должна принадлежать диапазону [x − d, x], а координата y – диапазону [y − d, y + d]. Поэтому доста- точно рассмотреть только точки, находящиеся в этой области, что и делает алгоритм эффективным. На рис. 13.20 область внутри штрихового контура содержит точки, которые могут находиться на расстоянии, не большем d
от текущей.
1
Создание эффективного алгоритма нахождения ближайшей пары точек когда-то было важной не- решенной задачей вычислительной геометрии. В конце концов, Шамос и Хоуи [30] придумали алго- ритм типа «разделяй и властвуй», работающий за время O(n log n). Представленный в этом разделе алгоритм на основе заметающей прямой имеет с ним общие черты, но проще в реализации.

258 
Глава 13. Геометрия d
d
Рис. 13.20. Область, в которой должна находиться ближайшая точка
Эффективность алгоритма основана на том фак- те, что эта область всегда содержит лишь O(1)точек.
Чтобы понять, почему это так, обратимся к рис. 13.21.
Поскольку текущее минимальное расстояние меж- ду двумя точками равно d, каждый квадрат размера
d/2×d/2 может содержать не более одной точки. А раз так, то во всей области не может быть больше восьми точек.
Перебрать все точки можно за время O(log n), если хранить множество точек с координатой x в диапазо- не [x − d, x] отсортированными в порядке возрастания координаты y. Временная сложность алгоритма равна
O(n log n), поскольку нам нужно просмотреть n точек и для каждой определить ближайшую к ней слева, для чего необходимо время O(log n).
13.2.3. Задача о выпуклой оболочке
Выпуклой оболочкой называется наименьший выпуклый многоугольник, содержащий все точки заданного множества. Здесь слово «выпуклый» озна- чает, что если две точки находятся внутри многоугольника, то внутри нахо- дится и весь отрезок между ними. На рис. 13.22 показана выпуклая оболочка множества точек.
Рис. 13.22. Выпуклая оболочка множества точек d
d
Рис. 13.21. Область ближайших точек содержит O(1) точек

13.2. Алгоритмы на основе заметающей прямой

259
Существует много эффективных алгоритмов построения выпуклой обо- лочки. Пожалуй, самым простым является описываемый ниже алгоритм
Эндрю [2]. Сначала алгоритм находит самую левую и самую правую точку множества, затем строит верхнюю и нижнюю части выпуклой оболочки.
Обе части похожи, так что можно ограничиться только верхней.
Сначала точки сортируются по координате x, а если координаты x двух точек совпадают, то по координате y. Затем мы просматриваем все точки и добавляем их в оболочку. Добавив очередную точку в оболочку, мы смот- рим, поворачивает ли последний отрезок налево. Если да, то мы удаляем предпоследнюю точку из оболочки и повторяем проверку. На рис. 13.23 показано, как алгоритм Эндрю строит верхнюю выпуклую оболочку для нашего множества точек.
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Шаг 5
Шаг 6
Шаг 7
Шаг 8
Шаг 8
Шаг 10
Шаг 11
Шаг 12
Шаг 13
Шаг 14
Шаг 15
Шаг 16
Шаг 17
Шаг 18
Шаг 19
Шаг 20
Рис. 13.23. Построение верхней части выпуклой оболочки с помощью алгоритма Эндрю