Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф. Скорины»
Математический факультет
Кафедра МПМ
Реферат
Геометрические задачи на олимпиадах по информатике
Исполнитель: Студентка группы М-31
Селиванцова А.Ю.
Научный руководитель:
Канд. физ-мат. наук, доцент Лебедева М.Т.
Гомель 2007
Содержание
Введение
1. Основные формулы и алгоритмы
2. Численное решение геометрических задач
3. Различные задачи
Заключение
Литература
Введение На большинстве многих областных олимпиадах по информатике по крайней мере одна из задач связана с геометрическими понятиями. Причем сформулированы они чаще всего в терминах вычислительной геометрии и описание таких объектов как прямая, отрезок, окружность, треугольник и т.д. производится путем задания координат точек, характеризующих эти объекты, в той или иной системе координат. Прежде, чем мы перейдем к рассмотрению этого класса олимпиадных задач, перечислим элементарные подзадачи (иногда это просто формулы из курса математики), на решение которых обычно опираются решения задач вычислительной геометрии.
1. Основные формулы и алгоритмы Большинство из перечисленных задач либо не требуют пояснений, либо приведены в [1-4]. Напомним лишь наиболее важные из них. Причем основным инструментом для построения наиболее простых формул во многих задачах вычислительной геометрии является векторное произведение. Поэтому рассмотрение начнем с вопросов, с ним связанных.
Косое произведение в задачах вычислительной геометрии
Под косым произведением векторов p1 и p2 с декартовыми координатами (x1, y1) и (x2, y2) можно понимать ориентированную площадь параллелограмма, образованного точками (0,0), (x1, y1), (x2, y2), (x1 + x2, y1 + y2), которая равна p1´p2 = –p2´p1= x1y2 – x2y1 (задача 5.5). Косое произведение напрямую связано с понятием векторного произведения (но в отличие от последнего это скаляр). Поэтому в литературе по вычислительной геометрии иногда используется именно ито понятие. По-другому косое произведение как и векторное обозначается [p1,p2]. Если два вектора провести из общей начальной точки, то их косое произведение больше нуля, если угол между первым и вторым вектором ориентирован также как угол между первым и вторым базисными векторами и меньше нуля — в противном случае. Косое произведение ненулевых векторов равно нулю тогда и только тогда, когда они коллинеарны (сонаправлены или противоположно направлены).
В задаче 3.2 проверить наличие пересечения у двух отрезков (а зачастую нас интересует лишь сам факт пересечения) несложно именно с использованием косого произведения. Пусть первый отрезок задан точками p1 и p2, а второй — p3 и p4 (также обозначаются вектора с соответствующими координатами). Обозначим xmax1 и xmin1 — максимальную и минимальную из первых координат первого отрезка, xmax2 и xmin2 — то же для второго отрезка. Для второй координаты аналогично имеем ymax1, ymin1, ymax2 и ymin2. Упомянутые отрезки пересекаются тогда, когда
а) пересекаются ограничивающие их прямоугольники, т.е. ............
