Міністерство освіти Республіки Білорусь
Установа освіти
В«Гомельський державний університет ім. Ф. Скорини В»
Математичний факультет
Кафедра МПМ
Реферат
Геометричні задачі на олімпіадах з інформатики
Виконавець: Студентка групи М-31
Селіванцова А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент Лебедєва М.Т.
Гомель 2007
Зміст
Введення
1. Основні формули і алгоритми
2. Чисельне рішення геометричних задач
3. Різні завдання
Висновок
Література
Введення
На більшості багатьох обласних олімпіадах з інформатики принаймні одне із завдань пов'язана з геометричними поняттями. Причому сформульовані вони найчастіше в термінах обчислювальної геометрії та опис таких об'єктів як пряма, відрізок, окружність, трикутник і т.д. виробляється шляхом завдання координат точок, характеризують ці об'єкти, в тій чи іншій системі координат. Перш, ніж ми перейдемо до розгляду цього класу олімпіадних завдань, перерахуємо елементарні підзадачі (іноді це просто формули з курсу математики), на вирішення яких зазвичай спираються рішення задач обчислювальної геометрії.
1. Основні формули і алгоритми
Більшість з перерахованих завдань або не вимагають пояснень, або приведені в [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 (також позначаються вектора з відповідними координатами). Позначимо x max 1 і x min 1 - максимальну і мінімальну з перших координат першого відрізка, x max 2 і x min 2 - Те ж для другого відрізка. Для другої координати аналогічно маємо y max 1 , y min 1 , y max 2 і y min 2 . Згадані відрізки перетинаються тоді, коли
а) перетинаються обмежують їх прямокутники, тобто x max 1 Ві x min 2 , x max 2 Ві x min 1 , y max 1 Ві y min 2 і y max 2 Ві y min 1 ;
б) косі твору ( p 3 - p 1 ) '( p 2 - p 1 ) і ( p 4 - p 1 ) '( p 2 - p 1 ) мають різний знак, точніше
[( p 3
