Computing Geometry Olymp 2024

---

Лекция 1. Базовая геометрия

Вопросы до или после лекций

Раскрой ...

1. Как доказать, что скалярное произведение векторов вычисляется по очень простой формуле:

$$\overrightarrow{u}\ast \overrightarrow{v}=(x_1,y_1)\ast (x_2,y_2)=x_1\cdot x_2+y_1\cdot y_2?$$

2. Что такое векторное произведение векторов?
3. Как задавать прямые в пространстве любой размерности
4. Как древнегреческие математики измеряли и обозначали углы?
5. В каких единицах измеряются углы в программах?
6. По какой формуле можно вычислить угол
   $\varphi$ в радианах, если даны координаты точки
   $(x,y)$ ?
7. Как найти
   $cos(2\varphi )$, если вам известно
   $cos(\varphi )$ ?
8. Как найти точное значение
   $cos(2\varphi )$,
   $cos(3\varphi )$,…,
   $cos(n\varphi )$ если вам известно точное значение
   $cos(\varphi )$ ?

---

---

Задачи

---

Точка на отрезке

https://www.eolymp.com/ru/problems/938

Точка на отрезке (desmos)
Точка на отрезке (geogebra)

"Уравнение отрезка":

Посмотрим...

Пусть на плоскости нам даны две точки

$p_1(x_1,y_1)$ и

$p_2(x_2,y_2)$, задающие концы отрезка, и произвольная точка

$p(x,y)$. Тогда для того, чтобы точка

$p$ лежала на отрезке

$\overline{p_1{p}_2}$, должно выполняться условие:

$r_1+r_2=r$,
или, после переноса

$r$ влево:

$r_1+r_2-r=0$,
где

$r_1$ – расстояние от точки

$p_1$ до точки

$p$,

$r_2$ – расстояние от точки

$p$ до точки

$p_2$,

$r$ – расстояние от точки

$p_1$ до точки

$p_2$.

Применяя теорему Пифагора или, что тоже самое, формулу вычисления длин векторов, получим на первый взгляд правильное выражение для точки

$p$, лежащей на отрезке

$\overline{p_1{p}_2}$:

$$\sqrt{(x-x_1{)}^2+(y-y_1{)}^2}+\sqrt{(x-x_2{)}^2+(y-y_2{)}^2}=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$$

В таком виде его нельзя применять в программах! (Почему?)
Вместо этого выражения нужно записать следующее:

$$|r_1+r_2-r|<ϵ$$

Где

$ϵ$ выбирается очень малым (в зависимости от задачи!). Например, можно в качестве пробного значения взять

$ϵ={10}^{-8}$.

---

Полярный угол точки

https://basecamp.eolymp.com/ru/problems/2129

---

Базовые вопросы и обсуждение

По какой формуле можно вычислить угол

$\varphi$ в радианах, если даны координаты

$(x,y)$ точки

$M$?

---

Переход от полярной системы координат к декартовой:

$x=\rho \cos \varphi$

$y=\rho \sin \varphi$

$\varphi =({\varphi }^{\circ })\ast \pi /{180}^{\circ }$

---

Вариант 1. Скалярное произведение векторов

Воспользуемся скалярным произведением векторов

$\overrightarrow{u}\ast \overrightarrow{v}$ :

$$\overrightarrow{u}\ast \overrightarrow{v}=u\cdot v\cdot \cos \varphi$$

Здесь

$u$ и

$v$ — размеры векторов, а

$\varphi$ — угол между ними.

---

Можно говорить, что скалярное произведение - это величина проекции одного вектора на другой ( промасштабированная размером второго вектора).

---

Тогда

$$\cos \varphi =\frac{\overrightarrow{u}\ast \overrightarrow{v}}{u\cdot v}$$

---

Пусть вектор

$\overrightarrow{u}=(3;4)$. Тогда

$u=5$.

Пусть

$\overrightarrow{v}=(1;0)$. Тогда

$v=1.$

$\overrightarrow{u}\ast \overrightarrow{v}=(3;4)\ast (1;0)=3\ast 1+4\ast 0=3$ :

Тогда

$\cos \varphi =3/5$.

---

Чему равняется

$\varphi$ ?

$$\varphi =\arccos (3/5)=0.927295218...rad={53}^{\circ }.130102354195...$$

---

У этого варианта есть серьезные недостатки - невозможность отличить положительные углы и отрицательные углы относительно оси x.

Похожие проблемы есть у всех обратных тригонометрических функций.

---

2 Вариант! Специальная функция для определения угла

Специальная функция, которая умеет точно отвечать на вопрос об угле точки

$(x;y),$ называетcя

$$\varphi =\text{atan2}(y,x)$$

Эта функция возвращает угол в диапазоне

$(-\pi ;\pi ]$

Уравнение прямой I

https://www.eolymp.com/ru/problems/2141

Уравнение прямой II

https://www.eolymp.com/ru/problems/2142

---

Общее уравнение прямой на плоскости

$$A\cdot x+B\cdot y+D=0$$

Обсуждение

---

Геометрический смысл коэффициентов уравнения

$\overrightarrow{N}=(A,B)$ — нормаль к прямой, управляет ее ориентацией и указывает на положительную полуплоскость.

$D$ — ненормированной расстояние от прямой до начала координат.

---

Условия

В данной задаче даны координаты двух точек :

$(x_1,y_1)$ и

$(x_2,y_2)$

Нам надо получить общее уравнение прямой, проходящей через эти две точки.

---

Решение

Воспользуемся отношениями подобия (или пропорциональности) изменений по

$x$ и

$y$ :

Возьмем первое из них и запишем в строчку :

$(x-x_1)(y_2-y_1)=(y-y_1)(x_2-x_1)$

---

Чуть раскроем скобки и немного упростим :

$x(y_2-y_1)-x_1{y}_2+x_1{y}_1=y(x_2-x_1)-y_1{x}_2+y_1{x}_1$

$x(y_2-y_1)-x_1{y}_2=y(x_2-x_1)-y_1{x}_2$

---

Перенесем все в левую часть и запишем относительно

$x$ и

$y$ :

$(y_2-y_1)x+(x_1-x_2)y-(x_1\ast y_2-y_1\ast x_2)=0$

Вспоминаем, что мы хотим получить уравнение

$$A\cdot x+B\cdot y+D=0$$

---

​​​​А это значит, что

$$\{\begin{array}{l}A=(y_2-y_1)\\ B=(x_1-x_2)\\ D=-(x_1{y}_2-y_1{x}_2)\end{array}$$

---

Проверяем.

При

$x_1=1,y_1=2,x_2=3,y_2=1$ мы получаем

$$\{\begin{array}{l}A=(1-2)=-1\\ B=(1-3)=-2\\ D=-(1\cdot 1-2\cdot 3)=5\end{array}$$

---

То есть, мы по двум заданным точкам

$S(1;2)$ и

$T(3;1)$ получили уравнение прямой
$$

⁍,
$$
проходящей через эти точки.

---

Действительно, при подстановке точки

$S(x_1;y_1)=S(1;2)$ в это уравнение мы получаем:

$$

-x_1-2y_1+5=0, \
-1-2\cdot 2+5=0, \
-5+5=0,
$$
верное равенство!

---

Аналогичный результат и при подстановке второй точки

$T(3;1)$.

---

Уравнение полуплоскости

Если мы заменим равенство на неравенство (cо знаком больше), мы получим следующее отношение:

$$⁍$$

---

Это отношение описывает полуплоскость с правой стороны при движении по прямой в направлении от первой точки S ко второй T:

---

Если же мы хотим, чтобы закрашенная полуплоскость появлялась с левой стороны по ходу движения вдоль линии — надо просто поменять знаки в (1).

---

Расстояния до прямой

Если мы подставим в общее выражение прямой

$$Ax+By+D$$
координаты произвольной точки

$P(x,y)$,
мы получим “расстояние” (ненормированное) от этой точки до прямой!

---

Причем, знак этого “расстояния” зависит от того, где точка

$P$ находится

• на полуплоскости(+)

• или вне ее (-) .

---

Чтобы получать нормальное расстояние, надо пронормировать выражение прямой, то есть разделить все коэффициенты на число

$N=|\overrightarrow{N}|=\sqrt{A^2+B^2}$.

$$a=A/N,b=B/N,d=D/N$$

Тогда

$\overrightarrow{n}=(a,b)$ - это тоже нормаль, как и

$\overrightarrow{N}$, только нормированная и

$|\overrightarrow{n}|=1!$

---

При этом

$d$ — это уже нормальное расстояние от прямой до начала координат (со знаком, зависящим от того, попадает ли начало координат в закрашенную область или находится с другой стороны).

---

Простые cистемы линейных уравнений. Формула Крамера

https://www.eolymp.com/uk/problems/936

Обсуждение

Детерминант

---

Важное выражение (детерминант).

Встречается во многих задачах компьютерной геометрии и при решении систем уравнений:

                    | x1  x2 |
det(x1,y1, x2,y2) = |        | = x1*y2 - x2*y1
                    | y1  y2 |

---

“Векторное” произведение.

Зная формулу для площади параллелограмма, мы можем ввести и использовать операцию “векторного” произведения векторов на плоскости:

---

$$\overrightarrow{u}\times \overrightarrow{v}=u\cdot v\cdot \sin \varphi =...$$

---

$$\overrightarrow{u}\times \overrightarrow{v}=det(\overrightarrow{u},\overrightarrow{v})=...$$

---

$$\overrightarrow{u}\times \overrightarrow{v}=det(x_1,y_1,x_2,y_2)=x_1{y}_2-x_2{y}_1$$

Параметрические уравнения

Параметрическое уравнение отрезка.
 Пусть

$A(x_1,y_1),B(x_2,y_2)$ – концы отрезка

$AB$.

Параметрическое уравнение отрезка имеет вид:

$S(t)=A+\overrightarrow{v}\cdot t$,

$\overrightarrow{v}=B-A=(x_2-x_1,y_2-y_1)$

$t\in [0,1]$
При

$t=0$ мы получаем точку

$A$, а при

$t=1$ — точку

$B$.

Параметрическое уравнение луча.

$R(t)=A+\overrightarrow{v}\cdot t$,

$t\in [0,\mathrm{\infty })$

Параметрическое уравнение линии.

$L(t)=A+\overrightarrow{v}\cdot t$,

$t\in (-\mathrm{\infty },\mathrm{\infty })$

Параметрическое уравнение плоскости

$\mathrm{\Pi }(s,t)=A+\overrightarrow{u}\cdot s+\overrightarrow{v}\cdot t$

Нормаль к плоскости или вектор, перпендикулярный двум другим векторам.

Если мы хотим построить нормаль

$\overrightarrow{n}$ к плоскости мы можем записать

$\overrightarrow{n}=\overrightarrow{u}\times \overrightarrow{v}$

Расстояние между отрезками 3d

https://www.eolymp.com/ru/problems/1830

def distance_from_two_lines(e1, e2, r1, r2):
    # e1, e2 = Direction vector
    # r1, r2 = Point where the line passes through

    # Find the unit vector perpendicular to both lines
    #  vector product: e1 x e2
    n = np.cross(e1, e2) 

    #  |n| = 1
    n /= np.linalg.norm(n)  

    # Calculate distance
    #  scalar product: n * (r1-r2)
    d = np.dot(n, r1 - r2)  

    return d

Треугольник и точка

https://basecamp.eolymp.com/ru/problems/666

---

Пересечение отрезков

https://basecamp.eolymp.com/ru/problems/714

https://basecamp.eolymp.com/ru/problems/839
https://basecamp.eolymp.com/ru/problems/1505

---

Формулы Крамера

https://www.eolymp.com/ru/contests/21305/problems/232342

---

Расстояние от точки до отрезка

https://www.eolymp.com/ru/problems/2138

Точка внутри круга

https://www.eolymp.com/ru/problems/3171

https://www.desmos.com/calculator/cybidko0g2

Две окружности

https://www.eolymp.com/ru/problems/4

Площадь многоугольника

https://www.eolymp.com/ru/problems/851

Площадь и объем пирамиды

https://www.eolymp.com/ru/problems/948

---

Сближение кораблей

https://www.eolymp.com/ru/problems/1421

---

Сложный (оптимизационный) подход к решению

Скорость каждого корабля преобразуем в декартову систему координат:

$$\overrightarrow{v}=(v\cos \varphi ,v\sin \varphi )$$

Используя параметрическое представление луча мы записываем два уравнения движения для кораблей:

$$\begin{array}{c}\overrightarrow{U}(t)=A+{\overrightarrow{v}}_1\ast t\\ \overrightarrow{V}(t)=B+{\overrightarrow{v}}_2\ast t\end{array}$$

---

Каждое из этих уравнений можно рассматривать как два уравнения:

$$\overrightarrow{V}(t)=\{\begin{array}{l}{V}_x(t)=B_x+v_{2x}\ast t\\ V_y(t)=B_y+v_{2y}\ast t\end{array}$$

---

Какое расстояние между кораблями?

Вектор

$\overrightarrow{\mathrm{\Delta }}$ от корабля

$\overrightarrow{V}$ к кораблю

$\overrightarrow{U}$:

$$\begin{gathered} \overrightarrow{\mathrm{\Delta }}=\overrightarrow{U}-\overrightarrow{V} \\ \overrightarrow{\mathrm{\Delta }}=(A_x+v_{1x}t-B_x-v_{2x}t,A_y+v_{1y}t-B_y-v_{2y}t). \end{gathered}$$
Длина вектора

$|\overrightarrow{\mathrm{\Delta }}|$ — расстояние между кораблями.

---

Рассмотрим квадрат расстояния между кораблями:

$w(t)=(\overrightarrow{U}-\overrightarrow{V}{)}^2={\overrightarrow{\mathrm{\Delta }}}^2=\overrightarrow{\mathrm{\Delta }}\ast \overrightarrow{\mathrm{\Delta }}$

Если расстояние между кораблями становится минимальным, то и квадрат расстояния становится минимальным.

---

Как найти минимум функции

Если скорость роста функции становится равной 0, то мы находимся

• либо минимуме,
• либо в максимуме,
• либо на “полочке” функции,

то есть, в какой-то экстремальной точке.

В нашей задаче мы должны получить минимум.

---

Как найти производную.

Нам сейчас достаточно запомнить простейшие случаи.

---

0. Производная константы
   $f(t)=c$ равна 0 (потому что константа никуда не растет).

---

1. Производная линейной функции
   $f(t)=t$:
   
   $$\frac{df(t)}{dt}=\frac{dt}{dt}=1$$

---

2. Производная квадратичной функции
   $f(t)=t^2$:
   
   $$\frac{df(t)}{dt}=\frac{d{t}^2}{dt}=2t$$

---

Распишем квадрат вектора

$\overrightarrow{\mathrm{\Delta }}=\overrightarrow{U}-\overrightarrow{V}$ , используя определение скалярного произведения:

$$\begin{gathered} w(t)=\overrightarrow{\mathrm{\Delta }}\ast \overrightarrow{\mathrm{\Delta }}=(A_x+v_{1x}t-B_x-v_{2x}t{)}^2+(A_y+v_{1y}t-B_y-v_{2y}t{)}^2 \\ w(t)=(A_x-B_x+(v_{1x}-v_{2x})t{)}^2+(A_y-B_y+(v_{1y}-v_{2y})t{)}^2 \end{gathered}$$

---

Найдем скорость изменения этой величины:

$$\frac{dw}{dt}=2(v_{1x}-v_{2x})(A_x-B_x+(v_{1x}-v_{2x})t)+2(v_{1y}-v_{2y})(A_y-B_y+(v_{1y}-v_{2y})t)$$

---

Для того, чтобы мы нашли минимум, мы должны решить уравнение:

$$\frac{dw}{dt}=0.$$

---

Мы получаем такое линейное уравнение относительно переменной

$t$:

$$\begin{gathered} (v_{1x}-v_{2x})(A_x-B_x+(v_{1x}-v_{2x})t)+(v_{1y}-v_{2y})(A_y-B_y+(v_{1y}-v_{2y})t)=0 \\ (v_{1x}-v_{2x})(A_x-B_x)+(v_{1x}-v_{2x}{)}^{2}t+(v_{1y}-v_{2y})(A_y-B_y)+(v_{1y}-v_{2y}{)}^{2}t=0 \\ (v_{1x}-v_{2x})(A_x-B_x)+(v_{1y}-v_{2y})(A_y-B_y)+((v_{1x}-v_{2x}{)}^2+(v_{1y}-v_{2y}{)}^2)t=0 \end{gathered}$$

---

Обозначим

$d=(v_{1x}-v_{2x})(A_x-B_x)+(v_{1y}-v_{2y})(A_y-B_y)$

$k=(v_{1x}-v_{2x}{)}^2+(v_{1y}-v_{2y}{)}^2$

Тогда

$$d+k\cdot t=0.$$

---

1. Решим его и получим момент времени
   $t$, когда корабли находятся на кратчайшем расстоянии.
2. Подставим это время в формулы (2), мы получим положения кораблей в момент наибольшего сближения.
3. Отсюда и находим минимальное расстояние между кораблями.

---

Если же время максимального сближения будет отрицательным, это значит, что корабли уже прошли точки максимального сближения и, поэтому ответ - расстояние

$|AB|$ между кораблями в момент времени

$t=0$.

Если

$k=0$, то корабли идут параллельными курсами и расстояние между ними всегда одно и то же.

---

Эту задачу можно решить и чисто геометрическими методами, если мы будем считать ось времени дополнительной пространственной осью.

---

Простой подход к решению

Человек-паук

https://www.eolymp.com/ru/problems/1682

Подход к решению

Пусть человек-паук находится в точке

$(x_i,y_i)$ и хочет прыгнуть на расстояние

$r$. Для нашей задачи достаточно считать, что

$r=1$.

Все возможные точки его прыжка описываются уравнением окружности:

$(x-x_i{)}^2+(y-y_i{)}^2=r^2$

Если человек-паук хочет прыгнуть на горизонтальную линию, то надо рассмотреть уравнение этой линии

$y=0$ и подставить это уравнение в уравнение окружности:

$(x-x_i{)}^2+y_i^2=r^2$

Тогда координата x следующей точки человека паука:

$x=x_i+\sqrt{r^2-y_i^2}$

Когда прыгать в эту точку опасно?
Когда:

$r^2-y_i^2<0$

Уравнение наклонной линии, идущей из начала координат под углом

$\alpha$:

$$⁍,$$

где

$k=\tan \alpha$

Как будет выглядеть пересечение этой линии с окружностью? Подставляем вместо

$y$ выражение

$kx$ и получаем:

$(x-x_i{)}^2+(kx-y_i{)}^2=r^2$

Раскроем скобки:

$x^2-2x{x}_i+x_i^2+k^2{x}^2-2kx{y}_i+y_i^2=r^2$

Приведем подобные и получим квадратное уравнение:

$(1+k^2)x^2-2(x_i+k{y}_i)x+x_i^2+y_i^2-r^2=0$

Пусть

$a=1+k^2$

$b=-2(x_i+k{y}_i)$

$c=x_i^2+y_i^2-r^2$

$D=b^2-4ac$

Наше квадратное уравнение примет вид:

$$⁍$$

Тогда новая координата

$x$ прыжка будет:

$$⁍$$

Когда прыгать в эту точку опасно? Когда:

$D<0$ .

Кроме того, надо учитывать то, что во время каждого следующего прыжка человек-паук должен быть еще дальше от начала координат….

Задачи 2 лекции

Конусное расстояние

https://www.eolymp.com/ru/problems/1501

Разворачиваем..

Вычисляем..

Выпуклый многоугольник

https://www.eolymp.com/ru/problems/2148

Закрашенные точки

Закрашенные точки

Выпуклая оболочка

https://www.eolymp.com/ru/problems/2294

Most distant points pair

https://www.eolymp.com/ru/problems/3167

Ближайшие точки

https://www.eolymp.com/ru/problems/555

Точка пересечения медиан

https://www.eolymp.com/ru/problems/5185

Центр вписанной окружности

https://www.eolymp.com/ru/problems/5186

Точка пересечения высот

https://www.eolymp.com/ru/problems/5187

Построить треугольник по двум сторонам и углу

https://www.eolymp.com/ru/problems/5190

Построить треугольник 2

https://www.eolymp.com/ru/problems/5191

Ссылки для самостоятельного ознакомления

Dot product - Wikipedia

Векторное произведение - Википедия

Find shortest distance between lines in 3D

GeoGebra Tutorial - Points and Vectors

Geometry Tool

Базовые соотношения и алгоритмы геометрии (RU)

5 Mathematics

5.1 Arithmetics and Geometry

Included Topics (✓)

• Integers:
  ✓ Operations (addition, subtraction, multiplication, division, exponentiation)
  ✓ Comparison (ordering, inequalities)
  ✓ Basic properties (sign, parity, divisibility)
• Basic modular arithmetic:
  ✓ Addition, subtraction, multiplication
• Prime numbers
• Fractions and percentages
• Geometric shapes:
  ✓ Line, line segment, angle
  ✓ Triangle, rectangle, square, circle
• Coordinate geometry:
  ✓ Points and vectors in the plane
  ✓ Coordinates and Euclidean distances
• Polygons:
  ✓ Vertex, side/edge
  ✓ Simple vs. convex polygons
  ✓ Concepts of "inside" and area
• Pythagorean theorem

---

Excluded Topics (✗)

• Geometry in three or more dimensions
• Advanced modular arithmetic:
  ✗ Modular division and inverse elements
• Complex numbers
• Trigonometric functions
• General conics:
  ✗ Parabolas, hyperbolas, ellipses
• Floating-point computations:
  ✗ Precision analysis and optimization

AL10. Geometric Algorithms

In general, the ISC has a strong preference towards problems that can be solved using integer arithmetic to avoid precision issues. This may include representing some computed values as exact fractions, but extensive use of such fractions in calculations is discouraged. Additionally, if a problem uses two-dimensional objects, the ISC prefers problems in which such objects are rectilinear.

Covered Topics (✓)

• ✓ Representing points, vectors, lines, line segments
• ✓ Checking for collinear points, parallel/orthogonal vectors and clockwise turns (for example, by using dot products and cross products)
• ✓ Intersection of two lines
• ✓ Computing the area of a polygon from the coordinates of its vertices
• ✓ Checking whether a (general/convex) polygon contains a point
• ✓ Coordinate compression
• ✓ O(n log n) time algorithms for convex hull
• ✓ Sweeping line method

Excluded Topics (✗)

• ✗ Point-line duality
• ✗ Halfspace intersection, Voronoi diagrams, Delaunay triangulations
• ✗ Computing coordinates of circle intersections against lines and circles
• ✗ Linear programming in 3 or more dimensions and its geometric interpretations
• ✗ Center of mass of a 2D object
• ✗ Computing and representing the composition of geometric transformations if the knowledge of linear algebra gives an advantage