Computing Geometry Olymp 2024

--- slideOptions: theme: league --- # Computing Geometry Olymp 2024 ![](https://i.imgur.com/0lvC4Eg.png)  ----  # [Лекция 1. Базовая геометрия](*) # Вопросы до или после лекций <details> <summary> Раскрой ... </summary> 1. Как доказать, что скалярное произведение векторов вычисляется по очень простой формуле: $$ \vec u * \vec v = (x_1, y_1) * (x_2, y_2) = x_1 \cdot x_2 + y_1 \cdot y_2 ? $$ 2. Что такое векторное произведение векторов? 3. Как задавать прямые в пространстве любой размерности 4. Как древнегреческие математики измеряли и обозначали углы? 5. В каких единицах измеряются углы в программах? 6. По какой формуле можно вычислить угол $\phi$ в радианах, если даны координаты точки $(x,y)$ ? 7. Как найти $cos(2\phi)$, если вам известно $cos(\phi)$ ? 8. Как найти **точное** значение $cos(2\phi)$, $cos(3\phi)$,...,$cos(n\phi)$ если вам известно **точное** значение $cos(\phi)$ ? </details> ---  ---  ## [Задачи](*) ---  ### [Точка на отрезке](https://www.eolymp.com/ru/problems/938) <img alt="Точка на отрезке" src="https://hackmd.io/_uploads/Hy5x0rj3T.png" width=300> [https://www.eolymp.com/ru/problems/938](https://www.eolymp.com/ru/problems/938) [Точка на отрезке (desmos)](https://www.desmos.com/calculator/qi4kyjx65f?lang=ru) [Точка на отрезке (geogebra)](https://www.geogebra.org/calculator/u68m57fk) #### "Уравнение отрезка": <details> <summary>Посмотрим...</summary> Пусть на плоскости нам даны две точки $p_1(x_1,y_1)$ и $p_2(x_2,y_2)$, задающие концы отрезка, и произвольная точка $p(x,y)$. Тогда для того, чтобы точка $p$ лежала на отрезке $\overline{p_1p_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_1p_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} $$ **В таком виде его нельзя применять в программах!** (*Почему?*) Вместо этого выражения нужно записать следующее: $$ \left| r_1 + r_2 - r \right| \lt \epsilon $$ Где $\epsilon$ выбирается очень малым (в зависимости от задачи!). Например, можно в качестве пробного значения взять $\epsilon = 10^{-8}$. </details> ---  ### [Полярный угол точки](https://basecamp.eolymp.com/ru/problems/2129) [https://basecamp.eolymp.com/ru/problems/2129](https://basecamp.eolymp.com/ru/problems/2129) ---  ![Полярный угол точки](https://i.imgur.com/Z2tiOTw.png) <details><summary>Базовые вопросы и обсуждение </summary> По какой формуле можно вычислить угол $\phi$ в радианах, если даны координаты $(x,y)$ точки $M$? ----  **Переход от полярной системы координат к декартовой:** $x = \rho \cos \phi$ $y= \rho \sin \phi$ $\phi= (\phi^\circ)*\pi / 180^\circ$ ----  ### Вариант 1. Скалярное произведение векторов Воспользуемся скалярным произведением векторов $\vec u * \vec v$ : $$ \vec u * \vec v = u \cdot v \cdot \cos \phi $$ Здесь $u$ и $v$ — размеры векторов, а $\phi$ — угол между ними. ----  Можно говорить, что скалярное произведение - это величина проекции одного вектора на другой ( промасштабированная размером второго вектора). ----  Тогда $$ \cos \phi = {\vec u * \vec v \over u \cdot v } $$ ---- Пусть вектор $\vec u = (3; 4)$. Тогда $u=5$. Пусть $\vec v = (1; 0)$. Тогда $v=1.$ $\vec u * \vec v = (3; 4) * (1; 0) = 3*1 +4*0 = 3$ : Тогда $\cos \phi = 3/5$. ---- Чему равняется $\phi$ ? $$ \phi = \arccos (3/5)= 0.927295218... rad = {53}^\circ.130102354195... $$ ---- ***У этого варианта есть серьезные недостатки - невозможность отличить положительные углы и отрицательные углы относительно оси x.*** Похожие проблемы есть у всех обратных тригонометрических функций. ---- ### 2 Вариант! Специальная функция для определения угла Специальная функция, которая умеет точно отвечать на вопрос об угле точки $(x;y),$ называетcя $$ \phi = \text{atan2} (y, x) $$ Эта функция возвращает угол в диапазоне $(-\pi; \pi]$ </details> ---  ### [Уравнение прямой I](https://www.eolymp.com/ru/problems/2141) ![Уравнение прямой I](https://i.imgur.com/dgWklvH.png) [https://www.eolymp.com/ru/problems/2141](https://www.eolymp.com/ru/problems/2141) ### [Уравнение прямой II](https://www.eolymp.com/ru/problems/2142) ![Уравнение прямой II](https://i.imgur.com/4MnZ6EF.png) [https://www.eolymp.com/ru/problems/2142](https://www.eolymp.com/ru/problems/2142) ----  ### Общее уравнение прямой на плоскости $$ A \cdot x + B\cdot y + D = 0 $$ <details><summary> Обсуждение </summary> ---- #### Геометрический смысл коэффициентов уравнения $\vec N = (A, B)$ — нормаль к прямой, управляет ее ориентацией и указывает на положительную полуплоскость. $D$ — ненормированной расстояние от прямой до начала координат. ![Untitled](Untitled%202.png) ---- #### Условия В данной задаче даны координаты двух точек : $(x_1, y_1)$ и $(x_2, y_2)$ Нам надо получить общее уравнение прямой, проходящей через эти две точки. ---- #### Решение Воспользуемся отношениями подобия (или пропорциональности) изменений по $x$ и $y$ : ![Untitled](Untitled%203.png) Возьмем первое из них и запишем в строчку : $(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*y_2 -y_1*x_2)= 0$ Вспоминаем, что мы хотим получить уравнение $$ A \cdot x + B\cdot y + D = 0 $$ ---- А это значит, что $$ \begin{equation} \begin{cases} A = (y_2 - y_1) \\ B = (x_1 - x_2) \\ D = -(x_1 y_2 - y_1 x_2) \\ \end{cases} \end{equation} $$ ---- Проверяем. При $x_1=1, y_1=2, x_2=3, y_2 =1$ мы получаем $$ \begin{cases} A = (1 - 2) = -1 \\ B = (1 - 3) = -2\\ D = -(1 \cdot 1 - 2 \cdot 3)= 5 \\ \end{cases} $$ ---- То есть, мы по двум заданным точкам $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)$. --- #### Уравнение полуплоскости ![](https://i.imgur.com/srYHu2j.png) Если мы заменим равенство на *неравенство* (cо знаком *больше*), мы получим следующее отношение: $$ ⁍ $$ ---- Это отношение описывает полуплоскость с правой стороны при движении по прямой в направлении от первой точки S ко второй T: ![Untitled](Untitled%204.png) ---- Если же мы хотим, чтобы закрашенная полуплоскость появлялась с левой стороны по ходу движения вдоль линии — надо просто поменять знаки в (1). ---  #### Расстояния до прямой Если мы подставим в общее выражение прямой $$ Ax +By +D $$ координаты произвольной точки $P(x,y)$, мы получим “расстояние” (ненормированное) от этой точки до прямой! ---  Причем, знак этого “расстояния” зависит от того, где точка $P$ находится + на полуплоскости(+) - или вне ее (-) . ![LineSigns](https://i.imgur.com/FIQSyUO.png "Line Signs" =400x) ----  Чтобы получать нормальное расстояние, надо пронормировать выражение прямой, то есть разделить все коэффициенты на число $N= |\vec N|= \sqrt{A^2+B^2}$. $$ a= A/N , \;\;\; b=B/N , \;\;\; d =D/N $$ Тогда $\vec n = (a,b)$ - это тоже нормаль, как и $\vec N$, только нормированная и $|\vec n|= 1!$ ----  При этом $d$ — это уже нормальное расстояние от прямой до начала координат (со знаком, зависящим от того, попадает ли начало координат в закрашенную область или находится с другой стороны). </details> ---  ### [Простые cистемы линейных уравнений. Формула Крамера](https://www.eolymp.com/uk/problems/936) https://www.eolymp.com/uk/problems/936 <details><summary>Обсуждение</summary> #### Детерминант ![Determinant](https://i.imgur.com/O5gLPDe.png "Determinant") ----  Важное выражение (детерминант). Встречается во многих задачах компьютерной геометрии и при решении систем уравнений: ```js | x1 x2 | det(x1,y1, x2,y2) = | | = x1*y2 - x2*y1 | y1 y2 | ``` --- #### “Векторное” произведение. Зная формулу для площади параллелограмма, мы можем ввести и использовать операцию “векторного” произведения векторов на плоскости: ----  $$ \vec u \times \vec v = u \cdot v \cdot \sin \phi = ... $$ ----  $$ \vec u \times \vec v = \det(\vec u, \vec v) = ... $$ ----  $$ \vec u \times \vec v = \det (x_1, y_1, \; x_2, y_2) = x_1y_2 - x_2y_1 $$ </details> --- ## ***Параметрические уравнения*** ***Параметрическое уравнение отрезка*.** Пусть $A(x_1, y_1), B(x_2, y_2)$ – концы отрезка $AB$. Параметрическое уравнение отрезка имеет вид: $S(t) = A + \vec v \cdot t$, $\vec v = B - A = (x_2-x_1 , y_2-y_1)$ $t \in [0, 1]$ При $t=0$ мы получаем точку $A$, а при $t=1$ — точку $B$. ***Параметрическое уравнение луча*.** $R(t) = A + \vec v \cdot t$, $t \in [0, \infty)$ ***Параметрическое уравнение линии*.** $L(t) = A + \vec v \cdot t$, $t \in (-\infty, \infty)$ ***Параметрическое уравнение плоскости*** $\Pi(s,t) = A + \vec u \cdot s + \vec v \cdot t$ ### Нормаль к плоскости или вектор, перпендикулярный двум другим векторам. Если мы хотим построить нормаль $\vec n$ к плоскости мы можем записать $\vec n = \vec u \times \vec v$ ### Расстояние между отрезками 3d [https://www.eolymp.com/ru/problems/1830](https://www.eolymp.com/ru/problems/1830) ![Расстояние между отрезками 3d](https://i.imgur.com/qMGmbey.png) ```python=1 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/666](https://basecamp.eolymp.com/ru/problems/666) ![TriangleHat](https://i.imgur.com/vJGq4oS.png "Triangle Hat" =400x) ---  ### [Пересечение отрезков](https://www.eolymp.com/ru/contests/21305/problems/232346) [https://basecamp.eolymp.com/ru/problems/714](https://basecamp.eolymp.com/ru/problems/714) [https://basecamp.eolymp.com/ru/problems/839]() [https://basecamp.eolymp.com/ru/problems/1505]() ![Cross](https://i.imgur.com/2B0vfwB.png "Cross" =400x) ---  ### [Формулы Крамера](https://www.eolymp.com/ru/contests/21305/problems/232342) [https://www.eolymp.com/ru/contests/21305/problems/232342](https://www.eolymp.com/ru/contests/21305/problems/232342) ![Cramer](https://i.imgur.com/djeqF5r.png "Cramer Rules" =400x) --- ### [Расстояние от точки до отрезка](https://www.eolymp.com/ru/problems/2138) [https://www.eolymp.com/ru/problems/2138](https://www.eolymp.com/ru/problems/2138) ![](https://i.imgur.com/oWyMuLR.png) ### Точка внутри круга [https://www.eolymp.com/ru/problems/3171](https://www.eolymp.com/ru/problems/3171) ![Точка внутри круга](https://i.imgur.com/BAmcupi.png) [https://www.desmos.com/calculator/cybidko0g2](https://www.desmos.com/calculator/cybidko0g2) ### Две окружности [https://www.eolymp.com/ru/problems/4](https://www.eolymp.com/ru/problems/4) ### Площадь многоугольника [https://www.eolymp.com/ru/problems/851](https://www.eolymp.com/ru/problems/851) ![Площадь многоугольника](https://i.imgur.com/DMkzXhH.png) ### Площадь и объем пирамиды [https://www.eolymp.com/ru/problems/948](https://www.eolymp.com/ru/problems/948) ![Площадь и объем пирамиды](https://i.imgur.com/HmuWzFw.png) ---  ### [Сближение кораблей](https://www.eolymp.com/ru/problems/1421) [https://www.eolymp.com/ru/problems/1421](https://www.eolymp.com/ru/problems/1421) <center> <img src=https://i.imgur.com/NxxmQza.png width=400 alt="Сближение кораблей"> </center> ---- <details><summary>Сложный (оптимизационный) подход к решению</summary>   Скорость каждого корабля преобразуем в декартову систему координат: $$ \vec v = (v\cos \phi , v\sin \phi) $$ Используя параметрическое представление луча мы записываем два уравнения движения для кораблей: $$ \begin{equation} \begin{matrix} \vec U(t) = A + \vec v_1 *t \\ \vec V(t) = B + \vec v_2 *t \end{matrix} \end{equation} $$ ----   Каждое из этих уравнений можно рассматривать как два уравнения: $$ \vec V(t)= \begin{cases} V_x(t) = B_x + v_{2x} *t \\ V_y(t) = B_y + v_{2y} *t \end{cases} $$ ----   Какое расстояние между кораблями? Вектор $\vec \Delta$ от корабля $\vec V$ к кораблю $\vec U$: $$ \vec \Delta = \vec U - \vec V \\ \vec\Delta = (A_x+v_{1x}t - B_x - v_{2x}t, A_y+v_{1y}t - B_y - v_{2y}t). $$ Длина вектора $|\vec \Delta|$ — расстояние между кораблями. ----   Рассмотрим квадрат расстояния между кораблями: $w(t) =(\vec U - \vec V)^2 = \vec \Delta ^2 = \vec \Delta * \vec \Delta$ Если расстояние между кораблями становится минимальным, то и квадрат расстояния становится минимальным. ----  **Как найти минимум функции** Если скорость роста функции становится равной 0, то мы находимся + либо минимуме, + либо в максимуме, + либо на “полочке” функции, ![Extremums](https://i.imgur.com/FtJqyb2.png "Extremums" =300x) то есть, в какой-то **экстремальной точке**. В нашей задаче мы должны получить минимум. ----  **Как найти производную.** Нам сейчас достаточно запомнить простейшие случаи. ----  0) Производная константы $f(t)=c$ равна 0 (потому что константа никуда не растет). ----  1) Производная линейной функции $f(t)=t$: $$ {df(t) \over dt } = {dt \over dt } = 1 $$ ----  2) Производная квадратичной функции $f(t)=t^2$: $$ {df(t) \over dt } = {dt^2 \over dt } = 2t $$ ----   Распишем квадрат вектора $\vec \Delta = \vec U - \vec V$ , используя определение скалярного произведения: $$ w(t) = \vec \Delta * \vec \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 $$ ----   Найдем скорость изменения этой величины: $$ {dw \over 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) $$ ----   Для того, чтобы мы нашли минимум, мы должны решить уравнение: $$ {dw \over dt} = 0. $$ ----   Мы получаем такое линейное уравнение относительно переменной $t$: $$ (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})^2t + (v_{1y} - v_{2y})(A_y - B_y) +(v_{1y} - v_{2y})^2t =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 $$ ----   Обозначим $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$, то корабли идут параллельными курсами и расстояние между ними всегда одно и то же. ----   Эту задачу можно решить и чисто геометрическими методами, если мы будем считать ось времени дополнительной пространственной осью. ---  </details> <details><summary>Простой подход к решению</summary> </details> ### Человек-паук [https://www.eolymp.com/ru/problems/1682](https://www.eolymp.com/ru/problems/1682) ![](https://i.imgur.com/k8EEQ7R.png) <details><summary>Подход к решению</summary> Пусть человек-паук находится в точке $(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 + (k x-y_i)^2 = r^2$ Раскроем скобки: $x^2-2xx_i +x_i^2 + k^2 x^2-2kxy_i +y_i^2 = r^2$ Приведем подобные и получим квадратное уравнение: $(1+k^2)x^2-2(x_i + ky_i)x +x_i^2 +y_i^2 - r^2 = 0$ Пусть $a= 1+k^2$ $b=-2(x_i+ky_i)$ $c=x_i^2 +y_i^2-r^2$ $D = b^2 -4ac$ Наше квадратное уравнение примет вид: $$ ⁍ $$ Тогда новая координата $x$ прыжка будет: $$ ⁍ $$ Когда прыгать в эту точку опасно? Когда: $D < 0$ . Кроме того, надо учитывать то, что во время каждого следующего прыжка человек-паук должен быть еще дальше от начала координат…. </details> # Задачи 2 лекции ### [Конусное расстояние](https://www.eolymp.com/ru/problems/1501) [https://www.eolymp.com/ru/problems/1501](https://www.eolymp.com/ru/problems/1501) ![](https://i.imgur.com/6JtHeKM.png) <details><summary>Разворачиваем..</summary> ![](https://i.imgur.com/dqsI9bJ.png) </details> <details><summary>Вычисляем..</summary> ![](https://i.imgur.com/SXZVRUi.png) </details> ### [Выпуклый многоугольник](https://www.eolymp.com/ru/problems/2148) [https://www.eolymp.com/ru/problems/2148](https://www.eolymp.com/ru/problems/2148) ### [Закрашенные точки](https://www.eolymp.com/ru/problems/297) [Закрашенные точки](https://www.eolymp.com/ru/problems/297) ### [Выпуклая оболочка](https://www.eolymp.com/ru/problems/2294) [https://www.eolymp.com/ru/problems/2294](https://www.eolymp.com/ru/problems/2294) ### [Most distant points pair](https://www.eolymp.com/ru/problems/3167) [https://www.eolymp.com/ru/problems/3167](https://www.eolymp.com/ru/problems/3167) ### [Ближайшие точки](https://www.eolymp.com/ru/problems/555) [https://www.eolymp.com/ru/problems/555](https://www.eolymp.com/ru/problems/555) ### [Точка пересечения медиан](https://www.eolymp.com/ru/problems/5185) [https://www.eolymp.com/ru/problems/5185](https://www.eolymp.com/ru/problems/5185) ### [Центр вписанной окружности](https://www.eolymp.com/ru/problems/5186) [https://www.eolymp.com/ru/problems/5186](https://www.eolymp.com/ru/problems/5186) ### [Точка пересечения высот](https://www.eolymp.com/ru/problems/5187) [https://www.eolymp.com/ru/problems/5187](https://www.eolymp.com/ru/problems/5187) ### [Построить треугольник по двум сторонам и углу](https://www.eolymp.com/ru/problems/5190) [https://www.eolymp.com/ru/problems/5190](https://www.eolymp.com/ru/problems/5190) ### [Построить треугольник 2](https://www.eolymp.com/ru/problems/5191) [https://www.eolymp.com/ru/problems/5191](https://www.eolymp.com/ru/problems/5191) # Ссылки для самостоятельного ознакомления [Dot product - Wikipedia](https://en.wikipedia.org/wiki/Dot_product) [Векторное произведение - Википедия](https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5) [Find shortest distance between lines in 3D](https://math.stackexchange.com/questions/2213165/find-shortest-distance-between-lines-in-3d) [GeoGebra Tutorial - Points and Vectors](http://www.malinc.se/math/geogebra/coordinatesen.php) [Geometry Tool](https://help.desmos.com/hc/en-us/articles/4405097945357-Geometry-Tool) [Базовые соотношения и алгоритмы геометрии (RU)](https://www.eolymp.com/uk/blogs/posts/25) # 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