Продовжуються заняття обласної школи олімпійського резерву з програмування.
14 жовтня відбулось перше заняття в режимі он-лайн. Присутні - учні шкіл Полтави та Кременчука. Тема заняття "Визначення положення точки відносно вектора". Розглянуті задачі:
1. Опукла оболонка. Задана множина з n точок на площині, жодні три з яких не лежать на одній прямій. Відомі координати цих точок. Визначити, які з них є вершинами опуклого многокутника, у середині якого містяться усі інші точки даної множини. Вивести вершини у порядку обходу.
2. Ламана. Задана множина з n точок на площині. Відомі координати цих точок. З'єднати дані точки у такій послідовності, щоб утворилася замкнена ламана, жодні дві сторони якої не перетинаються. Вивести координати вершин у порядку з'єднання.
3. Трикутник. Задані координати вершин трикутника АВС та точки М. Визначити, чи лежить точка усередині трикутника. Вивести 1, якщо точка усередині трикутника; 0 - якщо на його межах; -1 - якщо ззовні.
Додаткові завдання:
4. Для трьох точок на одній прямій визначити, як розташована третя точка по відношенню до перших двох.
5. Розв'язати задачу 1 за умови, що деякі три точки можуть лежати на одній прямій. Передбачити, що не потрібно виводити координати точок, що лежать на сторонах опуклої оболонки.
Наступне заняття Школи олімпійського резерву - у п'ятницю 21 жовтня об 11.00. Тема заняття "Теорія графів. Алгоритм Прима-Крускала".
Немає коментарів:
Дописати коментар