Міністерство освіти Республіки Білорусь
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПМ
Реферат
Геометричні задачі на олімпіадах з інформатики
Виконавець: Студентка групи М-31
Селіванцова А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент Лебедєва М.Т.
Гомель 2007
Зміст
Введення
1. Основні формули і алгоритми
2. Чисельне рішення геометричних задач
3. Різні завдання
Висновок
Література
Косе твір в задачах обчислювальної геометрії
Під косим добутком векторів 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 - 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, ..., p n -1, перерахованими в порядку його обходу проти годинникової стрілки, (завдання 6.4) можна обчислити як суму орієнтованих площ трикутників, утворених векторами p i і p i +1, i = 0, ..., n - 1; i + 1 обчислюється за модулем n.
Випуклість багатокутника (задача 6.2) з вершинами p 0, p 1, ..., p n -1, перерахованими в порядку його обходу, легко перевірити за допомогою порівняння знаків косого твори пар векторів (p i +1 - p i) і (p i +2 - p i +1), i = 0, ..., n - 1; i + 1 і i + 2 обчислюються за модулем n. У випадку опуклого багатокутника знаки у всіх зазначених творів збігаються (якщо ми знаємо напрямок обходу, то знак косих творів для опуклого багатокутника визначено: при обході за годинниковою стрілкою твори негативні, а проти годинникової стрілки - позитивні).
На цьому способи корисного застосування косого твори аж ніяк не вичерпано.
Опукла оболонка безлічі N точок площини
Завдання полягає в тому, щоб перерахувати всі точки, що належать кордоні опуклої оболонки заданої множини точок, в порядку її обходу, наприклад, проти годинникової стрілки (у деяких завданнях потрібно перерахувати тільки кутові точки). Для ефективного вирішення цієї задачі існує декілька різних алгоритмів (див. [1] - [4]). Наведемо найбільш просту реалізацію одного з них - алгоритму Джарвіса.
{Наступний абзац проілюструвати малюнком з номера 16/2000, стор 11}
Перерахування точок шуканої кордону опуклого багатокутника почнемо з правої нижньої точки, яка завідомо належить кордоні опуклої оболонки. Позначимо її координати (x 0, y 0). Наступною, при зазначеному порядку обходу, буде точка (x 1, y 1), для якої кут між віссю OX і вектором (x 0, y 0) - (x 1, y 1) мінімальний. Якщо таких точок декілька, то кутовий у багатокутнику стане точка, для якої довжина вектора (x 0, y 0) - (x 1, y 1) максимальна, а наступною точкою, яка належить опуклій оболонці - та, довжина вектора у якої мінімальна (таким чином наш вибір буде залежати від конкретної постановки задачі). Для знаходження наступної точки значення кутів між векторами обчислювати необов'язково. Ми знову можемо скористатися поняттям знака векторного добутку. Нехай, далі, ми вже знайшли i-у вершину опуклої оболонки (x i, y i). Тоді, (i + 1)-а точка є така точка, ще не увійшла в опуклу оболонку, для якої кут між вектором (x i -1, y i -1) - (x i, y i) і вектором (x i , y i) - (x i +1, y i +1) мінімальний, при мінімальній довжині вектора (x i, y i) - (x i +1, y i +1) серед усіх векторів з таким кутом. Зауважимо, що для всіх інших точок (x, y), вектор (x i, y i) - (x, y) буде лежати поза кута, утвореного зазначеними векторами, лівіше нього. Тоді векторний добуток (x i +1 - x i) (y - y i) - (y i +1 - y i) (x - x i) ³ 0, для будь-якої точки (x, y), ще не увійшла до кордон опуклої оболонки. Отже, ми можемо спочатку вважати наступної, (i + 1)-ої, будь-яку, ще не увійшла в опуклу оболонку, крапку, а потім, обчислюємо вказане вираз для інших "вільних" точок (х, y). Якщо для однієї з них (x i +1 - x i) (y - y i) - (y i +1 - y i) (x - x i) <0, вважаємо наступною її і продовжуємо перевірку інших точок (аналогічно алгоритму пошуку мінімального елемента в масиві). Якщо ж значення виразу дорівнює 0, то порівнюємо квадрати довжин векторів, а саме (x i +1 - x i) 2 + (y i +1 - y i) 2 і (x - x i) 2 + (y - y i ) 2.
Таким чином, при вирішенні даної задачі у випадку спочатку цілочисельних координат ми цілком можемо уникнути застосування речовій арифметики, а, отже, позбутися від втрати точності обчислень. В іншому випадку, в рішення можуть бути включені "зайві" точки, близькі до кордону опуклої оболонки або не враховані деякі з "потрібних" точок. Складність даного алгоритму складе O (kN), де k - кількість точок у опуклої оболонці, в гіршому випадку рівне N. Існують алгоритми вирішення цієї задачі, засновані на попередній сортування точок вихідної безлічі, наприклад, за значенням кута в полярній системі координат з центром в одній з точок опуклої оболонки, з обчислювальною складністю O (N log N) (алгоритм Грехема). Тобто найбільш трудомістким завданням виявляється саме сортування вихідних точок.
Наведемо програму вирішення даної задачі алгоритмом Джарвіса:
var a, b: array [1 .. 100] of record
x, y: integer;
f: boolean
end;
min, m, j, k, n: integer;
begin
readln (n);
for i: = 1 to n do
begin
read (a [i]. x, a [i]. y);
a [i]. f: = false
end;
{Шукаємо нижню праву точку}
m: = 1;
for i: = 2 to n do
if a [i]. y <a [m]. y then m: = i else
if (a [i]. y = a [m]. y) and
(A [i]. X> a [m]. X) then m: = i;
b [1]: = a [m];
a [m]. f: = true;
k: = 1;
repeat
min: = 1;
{Шукаємо перші ще вільну точку}
while a [min]. f do inc (min);
{Шукаємо чергову вершину опуклої оболонки}
for j: = 1 to n do
if (not a [j]. f) and
((A [min]. Xb [k]. X) * (a [j]. Yb [k]. Y) -
(A [j]. Xb [k]. X) * (a [min]. Yb [k]. Y) <0)
then min: = j else
if (not a [j]. f) and
((A [min]. Xb [k]. X) * (a [j]. Yb [k]. Y) -
(A [j]. Xb [k]. X) * (a [min]. Yb [k]. Y) = 0) and
(Sqr (a [min]. Xb [k]. X) + sqr (a [min]. Yb [k]. Y)>
sqr (a [j]. xb [k]. x) + sqr (a [j]. yb [k]. y))
then min: = j;
k: = k +1;
a [min]. f: = true;
b [k]: = a [min] {записана чергова вершина}
until min = m; {поки ламана не замкнеться}
for j: = 1 to k do {друк результату}
writeln (b [j]. x, '', b [j]. y);
end.
Наведемо приклади завдань, при вирішенні яких використовується побудова опуклої оболонки.
Завдання 1. Стіна. (В англомовному варіанті завдання пропонувалася на студентських командних змаганнях з програмування в Санкт-Петербурзі в 2001 р.)
Одного разу жадібний король наказав своєму архітектору побудувати стіну навколо палацу. Король був настільки жадібний, що не став слухати пропозиції архітектора про побудову стіни досконалої форми. Замість цього король наказав витратити на будівництво стіни певної висоти і довільної форми (не обов'язково у вигляді ламаної!) Якомога менше цеглин, але зажадав, щоб стіна відстояла від палацу не менше, ніж на L футів. У випадку невиконання умови або перевитрати коштів архітектор може позбутися голови.
Ваше завдання допомогти бідному архітекторові. Ваше завдання написати програму, яка визначить мінімально можливу довжину стіни, якою можна оточити палац і при цьому виконати всі вимоги короля.
Перший рядок вхідного файлу містить 2 числа N (3 £ N £ 1000) - кількість кутів у будівлі палацу і L (1 £ L £ 1000) мінімальна відстань на яке стіна може наближатися до палацу. Наступні N рядків описують координати на поверхні землі кутів палацу, в порядку їх обходу за годинниковою стрілкою. Кожен рядок містить два цілих числа - X i і Y i, розділених пробілом (-10000 £ X i, Y i £ 10000), які описую координати кутів палацу в футах. Всі кути палацу різні, а сторони не мають інших спільних точок, крім кутових.
Запишіть у вихідний файл одне число, що визначає мінімальну довжину палацу в футах, що задовольняє умові завдання. Відповідь повинна бути записана у вигляді цілого числа, так як з речовими числами король не знайомий, проте округляти його слід так, щоб ціле число футів відрізнялося від справжнього відповіді менш, ніж на 8 дюймів (в 1 фут 12 дюймів).
Рішення. Відповіддю на це завдання буде довжина опуклої оболонки, збільшена на довжину окружності з радіусом L і округлена до найближчого цілого.
Завдання 2. На площині задано N точок. Побудувати замкнуту ламану без самоперетинів і самокасаній, вершинами якої повинні стати всі задані точки. (Див., наприклад, [5], аналогічна завдання пропонувалася на кіровської обласній олімпіаді 2002р.).
Рішення. Наступний малюнок проілюструє ідею одного з можливих способів вирішення цієї задачі:
З чисельних методів найбільш часто вживаним є метод дихотомії (поділу навпіл). Розглянемо його на прикладі задачі XII Всеросійської олімпіади з інформатики.
Завдання 3. Розділ царства.
Царство царя Гороха являє собою опуклий N-кутник, всередині якого розташовані K селищ. Цар вирішив заповісти двом своїм синам за півцарства, однакові за площею і з рівною кількістю селищ. Для цього він вимагає розділити царство однієї прямолінійної кордоном.
Напишіть програму, що будує кордон згідно царській волі. Якщо межа проходить через селище, то воно може бути або віднесено до одного з напівцарством, або розділено на два села, які будуть віднесені до різних напівцарством (при непарній K кордон, природно, повинна розділити якийсь з селищ).
Перший рядок вхідного файлу містить кількість вершин багатокутника N (3 N 50). В наступних N рядках задано координати вершин багатокутника, перераховані в порядку обходу контуру за годинниковою стрілкою. В (N +2)-ої рядку вказано кількість селищ K (0 K 100), а в наступних K рядках задано координати селищ. Всі координати - цілі числа, не перевершують по модулю 10 6. Розмірами селищ варто знехтувати.
У вихідний файл потрібно вивести координати будь-яких двох різних точок, через які слід провести межу. Координати повинні бути виведені з 6 знаками після десяткової точки.
Рішення. Виберемо довільну точку на кордоні царства. Для пошуку прямої, що проходить через цю точку і ділить царство на дві рівні поки що тільки за площею частини, зафіксуємо дві інші точки кордону, так, що пряма проведена через обрану і першу з фіксованих точок ділить царство на дві нерівні частини, причому ліва (або нижня для горизонтальної прямої) частину менше правої (верхньої). Пряма ж, що проходить через обрану точку і другу з фіксованих, ділить царство у зворотному співвідношенні. Тоді шукана точка знаходиться між двома фіксованими і її можна шукати методом ділення навпіл. Тепер слід підрахувати кількість селищ у кожній з вже рівних за площею частин. Якщо воно різне, то на кордоні потрібно вибрати ще одну точку, при розподілі царства з допомогою якої кількість селищ у половинах також буде співвідноситися по-іншому. Тепер можна застосувати метод поділу навпіл для правильного вибору опорної точки.
Завдання 4. Рандеву. (VII Всеросійська олімпіада з інформатики.)
Локатори далекого космічного зв'язку помічають летить в площині орбіти землі невідомий астероїд з координатами (x, y). Астероїд летить з постійною швидкістю, векторне значення якої дорівнює (V x, V y). Із землі з точки з координатами (0, 0) негайно стартує ракета з радіусом дії R (R> 0). Ракета летить по прямій з постійною швидкістю в межах від 0 до W.
Потрібно визначити, чи може ракета підлетіти впритул до астероїда в межах радіуса її дії і знайти вектор швидкості ракети, при якому час зустрічі ракети з астероїдом мінімальне.
Результат розв'язання задачі має бути обчислено з похибкою не більше 0.01. Впливом землі і всіх космічних об'єктів знехтувати. Ракета і астероїд рухаються в одній площині.
На початку вхідного файлу міститься число N - кількість наборів вихідних даних (тестів). Далі розташовані N наборів вихідних даних, кожен набір - шість дійсних чисел: X, Y, V x, V y, W, R. Всі числа у вихідному файлі розділяються пробілами і (або) символами переведення рядка.
Для кожного набору вихідних даних вивести з нового рядка вектор швидкості (U x, U y) і мінімальний час до зустрічі, або повідомлення "Зустріч неможлива".
Рішення. Для вирішення цього завдання перш за все необхідно вміти визначати взаємне розташування прямої, уздовж якої рухається астероїд, та кола з центром на Землі і радіусом R. Якщо вони не перетинаються, то зустріч неможлива, в іншому випадку потрібно відшукати точки їх перетину. Потім для пошуку точки зустрічі з мінімальним часом можна знову ж застосувати дихотомію.
П'ятачок і Вінні-Пух щоранку ходять пити чай в гості до Кролика. Природно, самим коротким шляхом. На жаль, одного разу Вінні-Пуха прийшла в голову ідея вирити пастку для Слонопотама. Найприкріше, що вони з П'ятачком її навіть вирили. Тому тепер щоранку, йдучи в гості до Кролика, вони бояться в неї провалитися.
Напишіть програму, яка порахує довжину найкоротшого безпечного шляху від будиночка Вінні-Пуха до будиночка Кролика.
Пастка для Слонопотама представляє собою яму абсолютно круглої форми. Шлях є безпечним, якщо він не проходить по пастці (але може проходити по її межі).
У вхідному файлі записані спочатку координати будиночка Вінні-Пуха X В Y В, потім - координати будиночка Кролика X До Y К, а потім - координати центра та радіус пастки X Л Y Л R Л. Всі координати - цілі числа з діапазону від -32000 до 32000. Радіус пастки - натуральне число, не більше 32000.
Будиночки Вінні-Пуха і Кролика не можуть перебувати всередині пастки, але можуть перебувати на її кордоні.
Виведіть у вихідний файл одне число - довжину найкоротшого безпечного шляху від будиночка Вінні-Пуха до будиночка Кролика з трьома знаками після крапки.
Рішення. Для вирішення цього завдання необхідно визначати взаємне розташування кола та відрізка (а не прямий!) І правильно обчислювати довжину дуги кола, обмеженою двома заданими точками.
Завдання 6. Підсвітка фонтану. (IX Всеросійська олімпіада з інформатики)
Плоске дно фонтану описується замкнутої ламаної лінією без самоперетинів, причому ніякі три вершини ламаної не лежать на одній прямій. Для організації підсвічування фонтану між двома заданими кутами (вершинами) по дну прокладений гнучкий натягнутий кабель (див. рис.). Потрібно написати програму, яка обчислює довжину цього кабелю.
Вихідні дані записані у файлі в такій послідовності:
· У 1-ій рядку - число вершин N (N £ 100);
· В кожній з наступних N рядків - пари чисел через пробіл, які є координатами вершин x 1 y 1 x 2 y 2 ¼ x N y N в порядку обходу ламаної проти годинникової стрілки, де 1, 2 ,..., N - номери вершин;
· В останньому рядку - номери з'єднуються вершин k і l (1 £ k <l £ N).
Координати вершин є речовими числами.
Результат вивести у вигляді числа. Результат перевіряється з точністю до шести значущих цифр. Результуюче число може бути як з фіксованою точкою, так і в нормалізованому вигляді.
Рішення. Можливо кілька різних підходів до вирішення даної задачі. Один з них - пошук найкоротшого шляху у графі (див. лекцію 8), в матриці суміжності якого записано відстані між вершинами кордону фонтану, якщо їх можна прямо з'єднати шлангом і ¥, якщо цього зробити не можна. Для побудови такої матриці необхідно вміти перевіряти наявність перетину двох відрізків і в разі відсутності перетинів - місце розташування відрізка щодо кордону фонтану (всередині або зовні він знаходиться). В останній підзадачі досить визначити місцезнаходження однієї з внутрішніх точок цього відрізка.
Знання різних геометричних формул було необхідне і при вирішенні завдання XIII Всеросійської олімпіади з інформатики "Пожежа" (див. [7]).
2. Окулов С. М. Геометричні алгоритми. "Інформатика", № 15, 16, 17, 2000.
3. Окулов С.М. 100 завдань з інформатики. Кіров: вид-во ВДПУ, 2000.
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М. МЦНМО, 2000.
5. Андреєва О., Фаліна І. Турбо-Паскаль в школі. М.: Изд-во Бочкарьової Н.Ф., 1998.
6. Станкевич А. С. Рішення задач I Всеросійської командної олімпіади з програмування. "Інформатика", № 12, 2001.
7. Андреєва О. В. Рішення завдань XIII Всеросійської олімпіади з інформатики. "Інформатика", № 19, 2001.
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПМ
Реферат
Геометричні задачі на олімпіадах з інформатики
Виконавець: Студентка групи М-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 - 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, ..., p n -1, перерахованими в порядку його обходу проти годинникової стрілки, (завдання 6.4) можна обчислити як суму орієнтованих площ трикутників, утворених векторами p i і p i +1, i = 0, ..., n - 1; i + 1 обчислюється за модулем n.
Випуклість багатокутника (задача 6.2) з вершинами p 0, p 1, ..., p n -1, перерахованими в порядку його обходу, легко перевірити за допомогою порівняння знаків косого твори пар векторів (p i +1 - p i) і (p i +2 - p i +1), i = 0, ..., n - 1; i + 1 і i + 2 обчислюються за модулем n. У випадку опуклого багатокутника знаки у всіх зазначених творів збігаються (якщо ми знаємо напрямок обходу, то знак косих творів для опуклого багатокутника визначено: при обході за годинниковою стрілкою твори негативні, а проти годинникової стрілки - позитивні).
На цьому способи корисного застосування косого твори аж ніяк не вичерпано.
Опукла оболонка безлічі N точок площини
Завдання полягає в тому, щоб перерахувати всі точки, що належать кордоні опуклої оболонки заданої множини точок, в порядку її обходу, наприклад, проти годинникової стрілки (у деяких завданнях потрібно перерахувати тільки кутові точки). Для ефективного вирішення цієї задачі існує декілька різних алгоритмів (див. [1] - [4]). Наведемо найбільш просту реалізацію одного з них - алгоритму Джарвіса.
{Наступний абзац проілюструвати малюнком з номера 16/2000, стор 11}
Перерахування точок шуканої кордону опуклого багатокутника почнемо з правої нижньої точки, яка завідомо належить кордоні опуклої оболонки. Позначимо її координати (x 0, y 0). Наступною, при зазначеному порядку обходу, буде точка (x 1, y 1), для якої кут між віссю OX і вектором (x 0, y 0) - (x 1, y 1) мінімальний. Якщо таких точок декілька, то кутовий у багатокутнику стане точка, для якої довжина вектора (x 0, y 0) - (x 1, y 1) максимальна, а наступною точкою, яка належить опуклій оболонці - та, довжина вектора у якої мінімальна (таким чином наш вибір буде залежати від конкретної постановки задачі). Для знаходження наступної точки значення кутів між векторами обчислювати необов'язково. Ми знову можемо скористатися поняттям знака векторного добутку. Нехай, далі, ми вже знайшли i-у вершину опуклої оболонки (x i, y i). Тоді, (i + 1)-а точка є така точка, ще не увійшла в опуклу оболонку, для якої кут між вектором (x i -1, y i -1) - (x i, y i) і вектором (x i , y i) - (x i +1, y i +1) мінімальний, при мінімальній довжині вектора (x i, y i) - (x i +1, y i +1) серед усіх векторів з таким кутом. Зауважимо, що для всіх інших точок (x, y), вектор (x i, y i) - (x, y) буде лежати поза кута, утвореного зазначеними векторами, лівіше нього. Тоді векторний добуток (x i +1 - x i) (y - y i) - (y i +1 - y i) (x - x i) ³ 0, для будь-якої точки (x, y), ще не увійшла до кордон опуклої оболонки. Отже, ми можемо спочатку вважати наступної, (i + 1)-ої, будь-яку, ще не увійшла в опуклу оболонку, крапку, а потім, обчислюємо вказане вираз для інших "вільних" точок (х, y). Якщо для однієї з них (x i +1 - x i) (y - y i) - (y i +1 - y i) (x - x i) <0, вважаємо наступною її і продовжуємо перевірку інших точок (аналогічно алгоритму пошуку мінімального елемента в масиві). Якщо ж значення виразу дорівнює 0, то порівнюємо квадрати довжин векторів, а саме (x i +1 - x i) 2 + (y i +1 - y i) 2 і (x - x i) 2 + (y - y i ) 2.
Таким чином, при вирішенні даної задачі у випадку спочатку цілочисельних координат ми цілком можемо уникнути застосування речовій арифметики, а, отже, позбутися від втрати точності обчислень. В іншому випадку, в рішення можуть бути включені "зайві" точки, близькі до кордону опуклої оболонки або не враховані деякі з "потрібних" точок. Складність даного алгоритму складе O (kN), де k - кількість точок у опуклої оболонці, в гіршому випадку рівне N. Існують алгоритми вирішення цієї задачі, засновані на попередній сортування точок вихідної безлічі, наприклад, за значенням кута в полярній системі координат з центром в одній з точок опуклої оболонки, з обчислювальною складністю O (N log N) (алгоритм Грехема). Тобто найбільш трудомістким завданням виявляється саме сортування вихідних точок.
Наведемо програму вирішення даної задачі алгоритмом Джарвіса:
var a, b: array [1 .. 100] of record
x, y: integer;
f: boolean
end;
min, m, j, k, n: integer;
begin
readln (n);
for i: = 1 to n do
begin
read (a [i]. x, a [i]. y);
a [i]. f: = false
end;
{Шукаємо нижню праву точку}
m: = 1;
for i: = 2 to n do
if a [i]. y <a [m]. y then m: = i else
if (a [i]. y = a [m]. y) and
(A [i]. X> a [m]. X) then m: = i;
b [1]: = a [m];
a [m]. f: = true;
k: = 1;
repeat
min: = 1;
{Шукаємо перші ще вільну точку}
while a [min]. f do inc (min);
{Шукаємо чергову вершину опуклої оболонки}
for j: = 1 to n do
if (not a [j]. f) and
((A [min]. Xb [k]. X) * (a [j]. Yb [k]. Y) -
(A [j]. Xb [k]. X) * (a [min]. Yb [k]. Y) <0)
then min: = j else
if (not a [j]. f) and
((A [min]. Xb [k]. X) * (a [j]. Yb [k]. Y) -
(A [j]. Xb [k]. X) * (a [min]. Yb [k]. Y) = 0) and
(Sqr (a [min]. Xb [k]. X) + sqr (a [min]. Yb [k]. Y)>
sqr (a [j]. xb [k]. x) + sqr (a [j]. yb [k]. y))
then min: = j;
k: = k +1;
a [min]. f: = true;
b [k]: = a [min] {записана чергова вершина}
until min = m; {поки ламана не замкнеться}
for j: = 1 to k do {друк результату}
writeln (b [j]. x, '', b [j]. y);
end.
Наведемо приклади завдань, при вирішенні яких використовується побудова опуклої оболонки.
Завдання 1. Стіна. (В англомовному варіанті завдання пропонувалася на студентських командних змаганнях з програмування в Санкт-Петербурзі в 2001 р.)
Одного разу жадібний король наказав своєму архітектору побудувати стіну навколо палацу. Король був настільки жадібний, що не став слухати пропозиції архітектора про побудову стіни досконалої форми. Замість цього король наказав витратити на будівництво стіни певної висоти і довільної форми (не обов'язково у вигляді ламаної!) Якомога менше цеглин, але зажадав, щоб стіна відстояла від палацу не менше, ніж на L футів. У випадку невиконання умови або перевитрати коштів архітектор може позбутися голови.
Ваше завдання допомогти бідному архітекторові. Ваше завдання написати програму, яка визначить мінімально можливу довжину стіни, якою можна оточити палац і при цьому виконати всі вимоги короля.
Перший рядок вхідного файлу містить 2 числа N (3 £ N £ 1000) - кількість кутів у будівлі палацу і L (1 £ L £ 1000) мінімальна відстань на яке стіна може наближатися до палацу. Наступні N рядків описують координати на поверхні землі кутів палацу, в порядку їх обходу за годинниковою стрілкою. Кожен рядок містить два цілих числа - X i і Y i, розділених пробілом (-10000 £ X i, Y i £ 10000), які описую координати кутів палацу в футах. Всі кути палацу різні, а сторони не мають інших спільних точок, крім кутових.
Запишіть у вихідний файл одне число, що визначає мінімальну довжину палацу в футах, що задовольняє умові завдання. Відповідь повинна бути записана у вигляді цілого числа, так як з речовими числами король не знайомий, проте округляти його слід так, щоб ціле число футів відрізнялося від справжнього відповіді менш, ніж на 8 дюймів (в 1 фут 12 дюймів).
| Приклад вхідного файлу | Вихідний файл |
| 9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200 | 1628 |
Завдання 2. На площині задано N точок. Побудувати замкнуту ламану без самоперетинів і самокасаній, вершинами якої повинні стати всі задані точки. (Див., наприклад, [5], аналогічна завдання пропонувалася на кіровської обласній олімпіаді 2002р.).
Рішення. Наступний малюнок проілюструє ідею одного з можливих способів вирішення цієї задачі:
2. Чисельне рішення геометричних задач
У ряді випадків при рішенні геометричних задач формули з обчислювальної геометрії можуть виявитися занадто громіздкими і приводять до рішення нелінійних рівнянь. Тоді на допомогу можуть прийти чисельні (наближені) методи, що дозволяють вирішити задачу за необхідний час і з потрібною точністю. Такий підхід був продемонстрований в [6] при розгляді завдання "Фонтан" (її не слід плутати з завданням 6, наведеної нижче).З чисельних методів найбільш часто вживаним є метод дихотомії (поділу навпіл). Розглянемо його на прикладі задачі XII Всеросійської олімпіади з інформатики.
Завдання 3. Розділ царства.
Царство царя Гороха являє собою опуклий N-кутник, всередині якого розташовані K селищ. Цар вирішив заповісти двом своїм синам за півцарства, однакові за площею і з рівною кількістю селищ. Для цього він вимагає розділити царство однієї прямолінійної кордоном.
Напишіть програму, що будує кордон згідно царській волі. Якщо межа проходить через селище, то воно може бути або віднесено до одного з напівцарством, або розділено на два села, які будуть віднесені до різних напівцарством (при непарній K кордон, природно, повинна розділити якийсь з селищ).
Перший рядок вхідного файлу містить кількість вершин багатокутника N (3 N 50). В наступних N рядках задано координати вершин багатокутника, перераховані в порядку обходу контуру за годинниковою стрілкою. В (N +2)-ої рядку вказано кількість селищ K (0 K 100), а в наступних K рядках задано координати селищ. Всі координати - цілі числа, не перевершують по модулю 10 6. Розмірами селищ варто знехтувати.
У вихідний файл потрібно вивести координати будь-яких двох різних точок, через які слід провести межу. Координати повинні бути виведені з 6 знаками після десяткової точки.
| Приклад вхідного файлу | Приклад вихідного файлу |
| 4 10 Вересня 20 40 40 40 51 10 2 21 30 40 20 | 30.000000 35.000000 30.000000 15.000000 |
Завдання 4. Рандеву. (VII Всеросійська олімпіада з інформатики.)
Локатори далекого космічного зв'язку помічають летить в площині орбіти землі невідомий астероїд з координатами (x, y). Астероїд летить з постійною швидкістю, векторне значення якої дорівнює (V x, V y). Із землі з точки з координатами (0, 0) негайно стартує ракета з радіусом дії R (R> 0). Ракета летить по прямій з постійною швидкістю в межах від 0 до W.
Потрібно визначити, чи може ракета підлетіти впритул до астероїда в межах радіуса її дії і знайти вектор швидкості ракети, при якому час зустрічі ракети з астероїдом мінімальне.
Результат розв'язання задачі має бути обчислено з похибкою не більше 0.01. Впливом землі і всіх космічних об'єктів знехтувати. Ракета і астероїд рухаються в одній площині.
На початку вхідного файлу міститься число N - кількість наборів вихідних даних (тестів). Далі розташовані N наборів вихідних даних, кожен набір - шість дійсних чисел: X, Y, V x, V y, W, R. Всі числа у вихідному файлі розділяються пробілами і (або) символами переведення рядка.
Для кожного набору вихідних даних вивести з нового рядка вектор швидкості (U x, U y) і мінімальний час до зустрічі, або повідомлення "Зустріч неможлива".
| Приклад файлу вихідних даних | Приклад вихідного файлу |
| 2 5.3 2.8 10.6 5.6 11.0 50.0 3.0 -4.0 -3.0 4.0 5.0 10.0 | Зустріч неможлива 3.0 -4.0 0.5 |
3. Різні завдання
Завдання 5. "Куди йдемо ми з П'ятачком?" (Кіровське відкрите командна першість з програмування, 2001 р.)П'ятачок і Вінні-Пух щоранку ходять пити чай в гості до Кролика. Природно, самим коротким шляхом. На жаль, одного разу Вінні-Пуха прийшла в голову ідея вирити пастку для Слонопотама. Найприкріше, що вони з П'ятачком її навіть вирили. Тому тепер щоранку, йдучи в гості до Кролика, вони бояться в неї провалитися.
Напишіть програму, яка порахує довжину найкоротшого безпечного шляху від будиночка Вінні-Пуха до будиночка Кролика.
Пастка для Слонопотама представляє собою яму абсолютно круглої форми. Шлях є безпечним, якщо він не проходить по пастці (але може проходити по її межі).
У вхідному файлі записані спочатку координати будиночка Вінні-Пуха X В Y В, потім - координати будиночка Кролика X До Y К, а потім - координати центра та радіус пастки X Л Y Л R Л. Всі координати - цілі числа з діапазону від -32000 до 32000. Радіус пастки - натуральне число, не більше 32000.
Будиночки Вінні-Пуха і Кролика не можуть перебувати всередині пастки, але можуть перебувати на її кордоні.
Виведіть у вихідний файл одне число - довжину найкоротшого безпечного шляху від будиночка Вінні-Пуха до будиночка Кролика з трьома знаками після крапки.
| Приклади вхідного файлу | Приклади вихідного файлу |
| 0 0 0 1 10 10 1 | 1.000 |
| 5 0 0 5 0 0 5 | 7.854 |
| -5 0 5 0 0 0 3 | 11.861 |
Завдання 6. Підсвітка фонтану. (IX Всеросійська олімпіада з інформатики)
Плоске дно фонтану описується замкнутої ламаної лінією без самоперетинів, причому ніякі три вершини ламаної не лежать на одній прямій. Для організації підсвічування фонтану між двома заданими кутами (вершинами) по дну прокладений гнучкий натягнутий кабель (див. рис.). Потрібно написати програму, яка обчислює довжину цього кабелю.
Вихідні дані записані у файлі в такій послідовності:
· У 1-ій рядку - число вершин N (N £ 100);
· В кожній з наступних N рядків - пари чисел через пробіл, які є координатами вершин x 1 y 1 x 2 y 2 ¼ x N y N в порядку обходу ламаної проти годинникової стрілки, де 1, 2 ,..., N - номери вершин;
· В останньому рядку - номери з'єднуються вершин k і l (1 £ k <l £ N).
Координати вершин є речовими числами.
Результат вивести у вигляді числа. Результат перевіряється з точністю до шести значущих цифр. Результуюче число може бути як з фіксованою точкою, так і в нормалізованому вигляді.
| Приклад вхідного файлу | Приклад вихідного файлу | |
| 7 2 0 5 0 6 3.5 5 червня 2 квітня 7 березня 0 5 7 березня | 7.5 | |
Знання різних геометричних формул було необхідне і при вирішенні завдання XIII Всеросійської олімпіади з інформатики "Пожежа" (див. [7]).
Висновок
Т.ч., в даній роботі ми розглянули елементарні підзадачі, на вирішення яких звичайно спираються рішення задач обчислювальної геометрії, а також олімпіадні завдання, пов'язані з геометричними поняттями. У роботі наводяться докладні рішення задач з коментарями та поясненнями.Література
1. Препарату Ф., Шеймос М. Обчислювальна геометрія: введення. - М.: Світ, 1989.2. Окулов С. М. Геометричні алгоритми. "Інформатика", № 15, 16, 17, 2000.
3. Окулов С.М. 100 завдань з інформатики. Кіров: вид-во ВДПУ, 2000.
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М. МЦНМО, 2000.
5. Андреєва О., Фаліна І. Турбо-Паскаль в школі. М.: Изд-во Бочкарьової Н.Ф., 1998.
6. Станкевич А. С. Рішення задач I Всеросійської командної олімпіади з програмування. "Інформатика", № 12, 2001.
7. Андреєва О. В. Рішення завдань XIII Всеросійської олімпіади з інформатики. "Інформатика", № 19, 2001.