Задача 1
На площині задани дві точки А(х1, y1) и В(x2,y2). З'ясувати, який із відрізків - ОА або ОВ образує більший кут з віссю ОХ.
З курсу вищої алгебри відомо, що якщо D = x1*y2 - x2 * y1<0, то кут, - визначений точкою А більше, ніж кут, визначений точкою В; якщо D = 0, то кути рівні, і якщо D> 0 , то кут, утворений ОВ, більше.
наприклад:
A (-1, 3), B (0, -2), x1* y2-x2 * y1 = 2> 0,
і отже, відрізок ОА утворює менший кут з віссю ОХ (кути завжди відлічуються проти годинникової стрілки!).
Задача 2
З'ясувати чи належить точка А відрізку з кінцями у точках В та С.
Як визначити, чи належить точка А (х, у) відрізку з кінцевими точками B (xl, yl) і С (х2, у2)?
Точки відрізка z можна описати рівнянням
р*ОВ + (1-р)*OC = z, 0 <= р <= 1, ОВ і ОС - вектори.
Якщо існує таке р, 0 <= р <= 1, що р*ОВ + (1-р)*ОС = А, то А лежить на відрізку, інакше - ні.
Рівність розписується по координатно так:
p*x1 + (1-р)*х2 = х
p*y1 + (1-р)*у2 = у
З першого рівняння знаходимо р, підставляємо в друге: якщо отримуємо рівність і 0 <= р <= 1, то А на відрізку, інакше - ні.
Задача 3
1. Опуклий багатокутник задається координатами вершин при його обході за годинниковою або проти годинникової стрілки. Контур многокутника не має самопересічень. Визначити напрямок обходу.
2. Виконати те ж саме, але тільки у випадку неопуклого многокутника.
Розглянемо трохи іншу задачу:
Дано 2 точки A (x1, y1) і В (х2, у2). Визначити, який з відрізків, ОА або ОВ, утворює більший кут з віссю ОХ. (Попередня задача очевидним чином зводиться до цієї задачі 1). Якщо в умові задачі багатокутник неопуклий, то застосуємо наступний спосіб вирішення: знаходимо точку з максимальною абсцисою, і, йдучи вздовж контуру, дивимося: якщо перше невертикальне ребро відхиляється проти годинникової стрілки, то це обхід проти годинникової стрілки, інакше - ні.
На площині задани дві точки А(х1, y1) и В(x2,y2). З'ясувати, який із відрізків - ОА або ОВ образує більший кут з віссю ОХ.
З курсу вищої алгебри відомо, що якщо D = x1*y2 - x2 * y1<0, то кут, - визначений точкою А більше, ніж кут, визначений точкою В; якщо D = 0, то кути рівні, і якщо D> 0 , то кут, утворений ОВ, більше.
наприклад:
A (-1, 3), B (0, -2), x1* y2-x2 * y1 = 2> 0,
і отже, відрізок ОА утворює менший кут з віссю ОХ (кути завжди відлічуються проти годинникової стрілки!).
Задача 2
З'ясувати чи належить точка А відрізку з кінцями у точках В та С.
Як визначити, чи належить точка А (х, у) відрізку з кінцевими точками B (xl, yl) і С (х2, у2)?
Точки відрізка z можна описати рівнянням
р*ОВ + (1-р)*OC = z, 0 <= р <= 1, ОВ і ОС - вектори.
Якщо існує таке р, 0 <= р <= 1, що р*ОВ + (1-р)*ОС = А, то А лежить на відрізку, інакше - ні.
Рівність розписується по координатно так:
p*x1 + (1-р)*х2 = х
p*y1 + (1-р)*у2 = у
З першого рівняння знаходимо р, підставляємо в друге: якщо отримуємо рівність і 0 <= р <= 1, то А на відрізку, інакше - ні.
Задача 3
1. Опуклий багатокутник задається координатами вершин при його обході за годинниковою або проти годинникової стрілки. Контур многокутника не має самопересічень. Визначити напрямок обходу.
2. Виконати те ж саме, але тільки у випадку неопуклого многокутника.
Знайдемо якусь внутрішню точку А (х, у) опуклого багатокутника, наприклад, центр мас трьох послідовних точок на контурі: А (х, у) = ((х1 + х2 + х3) / 3; (y1+ y2 + y3) / 3).
На контурі виберемо довільно дві послідовні вершини L1 і L2 і обчислимо кути, які утворюють відрізки (A, L1) і (A, L2) з віссю ОХ. Якщо перший кут менше другого, то обхід проти годинникової стрілки, інакше - за годинниковою. Для обчислення кутів можна використовувати функцію arctan (x) в Pascal.
На контурі виберемо довільно дві послідовні вершини L1 і L2 і обчислимо кути, які утворюють відрізки (A, L1) і (A, L2) з віссю ОХ. Якщо перший кут менше другого, то обхід проти годинникової стрілки, інакше - за годинниковою. Для обчислення кутів можна використовувати функцію arctan (x) в Pascal.
Розглянемо трохи іншу задачу:
Дано 2 точки A (x1, y1) і В (х2, у2). Визначити, який з відрізків, ОА або ОВ, утворює більший кут з віссю ОХ. (Попередня задача очевидним чином зводиться до цієї задачі 1). Якщо в умові задачі багатокутник неопуклий, то застосуємо наступний спосіб вирішення: знаходимо точку з максимальною абсцисою, і, йдучи вздовж контуру, дивимося: якщо перше невертикальне ребро відхиляється проти годинникової стрілки, то це обхід проти годинникової стрілки, інакше - ні.