Геометрические задачи на олимпиадах по информатике
Исполнитель: Студентка группы М-31
Селиванцова А.Ю.
Научный руководитель:
Канд. физ-мат. наук, доцент Лебедева М.Т.
Гомель 2007
Содержание
Введение
1. Основные формулы и алгоритмы
2. Численное решение геометрических задач
3. Различные задачи
Заключение
Литература
Введение
На большинстве многих областных олимпиадах по информатике по крайней мере одна из задач связана с геометрическими понятиями. Причем сформулированы они чаще всего в терминах вычислительной геометрии и описание таких объектов как прямая, отрезок, окружность, треугольник и т.д. производится путем задания координат точек, характеризующих эти объекты, в той или иной системе координат. Прежде, чем мы перейдем к рассмотрению этого класса олимпиадных задач, перечислим элементарные подзадачи (иногда это просто формулы из курса математики), на решение которых обычно опираются решения задач вычислительной геометрии.
Основные формулы и алгоритмы
Большинство из перечисленных задач либо не требуют пояснений, либо приведены в [1-4]. Напомним лишь наиболее важные из них. Причем основным инструментом для построения наиболее простых формул во многих задачах вычислительной геометрии является векторное произведение. Поэтому рассмотрение начнем с вопросов, с ним связанных.
Косое произведение в задачах вычислительной геометрии
Под косым произведением векторов p 1 и p 2 с декартовыми координатами (x 1, y 1) и (x 2, y 2) можно понимать ориентированную площадь параллелограмма, образованного точками (0,0), (x 1, y 1), (x 2, y 2), (x 1 + x 2, y 1 + y 2), которая равна p 1´ p 2 = – p 2´ p 1= x 1 y 2 – x 2 y 1 (задача 5.5). Косое произведение напрямую связано с понятием векторного произведения (но в отличие от последнего это скаляр). Поэтому в литературе по вычислительной геометрии иногда используется именно ито понятие. По-другому косое произведение как и векторное обозначается [ p 1, p 2]. Если два вектора провести из общей начальной точки, то их косое произведение больше нуля, если угол между первым и вторым вектором ориентирован также как угол между первым и вторым базисными векторами и меньше нуля — в противном случае. Косое произведение ненулевых векторов равно нулю тогда и только тогда, когда они коллинеарны (сонаправлены или противоположно направлены).
В задаче 3.2 проверить наличие пересечения у двух отрезков (а зачастую нас интересует лишь сам факт пересечения) несложно именно с использованием косого произведения. Пусть первый отрезок задан точками p 1 и p 2, а второй — p 3 и p 4 (также обозначаются вектора с соответствующими координатами). Обозначим xmax 1 и xmin 1 — максимальную и минимальную из первых координат первого отрезка, xmax 2 и xmin 2 — то же для второго отрезка. Для второй координаты аналогично имеем ymax 1, ymin 1, ymax 2 и ymin 2. Упомянутые отрезки пересекаются тогда, когда
а) пересекаются ограничивающие их прямоугольники, т.е. xmax 1 ³ xmin 2, xmax 2 ³ xmin 1, ymax 1 ³ ymin 2 и ymax 2 ³ ymin 1;
б) косые произведения (p 3 – p 1)´(p 2 – p 1) и (p 4 – p 1)´(p 2 – p 1) имеют разный знак, точнее
[(p 3 – p 1),(p 2 – p 1)]×[(p 4 – p 1),(p 2 – p 1)] £ 0;
в) [(p 1 – p 3),(p 4 – p 4)]×[(p 2 – p 3),(p 4 – p 3)] £ 0.
Последние два условия означают, что концы одного отрезка лежат по разные стороны от прямой, которой принадлежит другой отрезок. Первое же условие исключает из специального рассмотрения случай равенства нулю всех четырех косых произведений, при котором отрезки лежат на одной прямой и могут как пересекаться, так и нет.
Площадь треугольника (задача 6.3) равна половине модуля косого произведения двух векторов, образованных любыми двумя его сторонами.
Тогда расстояние от точки C до прямой, заданной координатами точек A и B (задача 4.2), можно подсчитать как отношение модуля косого произведения векторов CA и CB к длине отрезка AB (данная формула следует из двух способов вычисления площади треугольника).
Площадь произвольного многоугольника с вершинами p 0, p 1, …, pn -1, перечисленными в порядке его обхода против часовой стрелки, (задача 6.4) можно вычислить как сумму ориентированных площадей треугольников, образованных векторами pi и pi +1, i = 0, …, n – 1; i + 1 вычисляется по модулю n.
Выпуклость многоугольника (задача 6.2) с вершинами p 0, p 1, …, pn -1, перечисленными в порядке его обхода, легко проверить с помощью сравнения знаков косого произведения пар векторов (pi +1 – pi) и (pi +2 – pi +1), i = 0, …, n – 1; i + 1 и i + 2 вычисляются по модулю n. В случае выпуклого многоугольника знаки у всех указанных произведений совпадают (если мы знаем направление обхода, то знак косых произведений для выпуклого многоугольника определен: при обходе по часовой стрелке произведения отрицательны, а против часовой стрелки — положительны).
На этом способы полезного применения косого произведения отнюдь не исчерпаны.