e-olymp 8357. Точка в многоугольнике

Задача

Как известно, простой многоугольник — это фигура, состоящая из не пересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.

Входные данные

В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные

Вывести строку «YES», если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

Входные данные Выходные данные
3 0 0
1 0
0 1
1 1
NO
4 3 2
0 0
1 5
5 5
6 0
YES
3 5 6
2 3
8 0
-1 -3
NO
4 -2 3
0 0
5 0
0 6
3 3
NO
5 3 1
9 2
3 0
-2 -4
-4 0
-4 5
YES

Код программы

Решение

Задача сводится к поиску площадей. Считаю площадь треугольника, образующегося тремя последовательными точками многоугольника. Далее считаю площади треугольников которые заданная точка образует с каждой парой точек из этой пары. Если площадь первого треугольника равна сумме площадей этих, то точка находится в треугольнике, а следовательно и в многоугольнике. Если нет перехожу к следующей тройке точек. Если точка не принадлежит ни одному треугольнику, то точка находится вне многоугольника.

Ссылки

e-olymp 143. Точка и треугольник

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

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

Входные данные

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

Выходные данные

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

Входные данные Выходные данные
1 2 6 -9 3 8 1 5 11 1
2 -13 10 -12 5 99 80 17 13 0
3 98 -50 -87 7 5 3 23 17 0
4 5 15 7 12 5 3 2 54 1
5 2 2 3 1 1 3 9 11 1

Код программы

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

 

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

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

Задача

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин на плоскости, определить имеют ли они общие точки.

Входные данные

Координаты концов отрезка[latex]AB[/latex] и [latex]CD[/latex].

Выходные данные

Пересекаются ли отрезки.

Тесты

Входные данные Выходные данные
[latex]x1[/latex] [latex]y1[/latex] [latex]x2[/latex] [latex]y2[/latex] [latex]x3[/latex] [latex]y3[/latex] [latex]x4[/latex] [latex]y4[/latex]
1 0 2 1 1 0 2 0 Отрезки пересекаются
-1 1 2 -2 0 -2 1 3 Отрезки пересекаются
1 1 2 2 2 2 1 1 Отрезки пересекаются
-1 1 -1 2 1 1 2 2 Отрезки не пересекаются
-2 -1 -2 3 0 -1 0 3 Отрезки не пересекаются
-2 0 0 2 0 -2 1 1 Отрезки не пересекаются

Код программы на C++

Код программы на Java

Решение

Пусть концы отрезков имеют координаты [latex]A(x_1,y_1)[/latex], [latex]B(x_2,y_2)[/latex], [latex]C(x_3,y_3)[/latex] и [latex]D(x_4,y_4)[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=u x_1+(1−u)x_2; \newline y=uy_1+(1−u)y_2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex]
$$\begin{cases}x=vx_3+(1−v)x_4 \newline y=vy_3+(1−v)y_4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex]
$$\begin{cases}ux_1+(1−u)x_2=vx_3+(1−v)x_4 \newline uy_1+(1−u)y_2=vy_3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y_4-y_3)\cdot(x_1-x_2)-(x_4-x_3)\cdot(y_1-y_2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x_4-x_2)\cdot(y_4-y_3)-(x_4-x_3)\cdot(y_4-y_2)}{denominator} \newline Ub=\frac{(x_1−x_2)\cdot(y_4−y_2)−(x_4−x_2)\cdot(y_1−y_2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone C++
Ideone Java

Mif 17.13

17_13

Задача №17.13

Условие

Принадлежит ли точка (х;у) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты

Входные данные (точка K) Выходные данные
(3;4) no
(1;1) yes
(1;4) yes
(3;0) yes
(0;6) no
(-13; -3) no
(-4.5; -3) yes

Код программы

Для запроса на выполнение нажать здесь.

Решение

[latex](x — x_A)(y_B — y_A) — (y — y_A)(x_B — x_A) = 0[/latex] — уравнение прямой, проходящей через точки [latex]A[/latex] и [latex]B[/latex]. Тогда для любой точки [latex](x; y)[/latex] можно определить её местоположение относительно прямой [latex]AB[/latex]. Если левая часть неравенства будет равно 0, то точка лежит на прямой. Прямая [latex]AB[/latex] разбивает плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения, а точки из другой полуплоскости — отрицательные. Тогда, объединением условий местоположения точки [latex](x; y)[/latex] и местоположения точек [latex]C, A, B[/latex] относительно прямых [latex]AB[/latex], [latex]BC[/latex], [latex]AC[/latex] соответственно, мы сможем определить местоположение данной точки относительно треугольника.

По рисунку видно, что [latex]A(1;4), B(5, -4), C(-5, -3)[/latex]. Тогда, определяем положение точки [latex]K[/latex] относительно каждой прямой и точки не лежащей на данной прямой треугольника [latex]ABC[/latex].

 

Mif 17.20

Задача. Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

1

Входные данные

Координаты точки в формате [latex](x, y)[/latex] ([latex]x, y[/latex] — действительные числа).

Выходные данные 

Вывести «YES», если точка принадлежит фигуре, и «NO» в противоположном случае.
(Точку, которая находится на контуре, также считаем принадлежащей данной фигуре).

Тесты

[latex]x[/latex] [latex]y[/latex]    Результат
0 0 YES
-5 -5 YES
0 2.5 YES
3.5 4.2 YES
-4 -2.7 YES
3 -4 NO
-2 -1.5 NO
1 6 NO
3.5 0.5 NO
1000 2 NO

 

Решение

Проанализировав фигуру, можно определить, что она не симметрична, хотя данное свойство было бы нам полезно. Однако мы имеем полное право выполнить параллельный перенос фигуры на [latex]0.5[/latex] единиц влево. Рассмотрим текущее расположение фигуры.

201Работать с фигурой стало проще, благодаря симметричности относительно начала координат [latex]O[/latex]. Для того чтобы не противоречить данному условию из-за выполненного сдвига, как только считываем координаты, уменьшаем абсциссу на [latex]0.5[/latex] единиц.
(На рисунке выделены основные данные, обозначенные определенными константами, которые понадобятся нам в ходе решения).

Для определения принадлежности точки фигуре будем постепенно убирать те области, в которых точка явно не может принадлежать фигуре:

  1. В первую очередь исключим все точки, у которых модули значений координат превышают [latex]5.5[/latex] по оси абсцисс или [latex]5[/latex] по оси ординат.
    (Условие проверки :  [latex]|y| > c [/latex]  [latex]\vee[/latex]  [latex]|x| > d [/latex] )
  2. Осталось рассмотреть две области, в которых точка не принадлежит фигуре тогда и только тогда, когда лежит ниже чем прямая [latex]y = 2[/latex] и правее [latex]x = 1.5[/latex] или же выше чем [latex]y = -2[/latex] и левее [latex]x =- 1.5[/latex].
    (Условие проверки :  [latex](x < -b[/latex]   [latex]\wedge[/latex]  [latex]y > -a)[/latex]  [latex]\vee[/latex]  [latex](x > b[/latex]  [latex]\wedge[/latex]  [latex]y < a)[/latex])
  3. Если хотя бы одно из предыдущих условий выполнилось, приходим к заключению, что точка не принадлежит данной фигуре. Выводим «NO».
    В противном случае выводим «YES».

Код программы:

 

Код программы

Mif 17.10

Задача

Принадлежит ли точка [latex]\left( x;y \right)[/latex] фигуре на рисунке?

2

 

Тесты

[latex]\left( x;y \right)[/latex] Ответ
1. (1;6) нет
2. (-5;3) нет
3. (0;0) нет
4. (3.5;1.7) да
5. (2;4) да

Код программы

ideone.com

Решение

Рисунок находится в I четверти, следовательно только точка с положительными [latex]x[/latex] и [latex]y[/latex] может принадлежать этому рисунку. Далее необходимо воспользоваться уравнением окружности [latex]\left(x-a \right)^2+\left(y-b \right)^2=R^2[/latex], т.к. центр окружности(сегмент которой изображен на рисунке) находится в начале координат формула имеет такой вид: [latex]x^2+y^2=R^2[/latex]. Также рисунок ограничен прямой [latex]y=3-x[/latex]. Если [latex]x>0[/latex] и [latex]y>0[/latex] ,  [latex]R\leq6[/latex] , [latex]y\geq3-x[/latex], то точка принадлежит фигуре на рисунке.

Mif 17.16

Условие

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

grph

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

Тестирование

Входные данные Выходные данные
1 0 0 Yes
2 -6 0 Yes
3 5.0 -2.0 Yes
4 -3.33 -5 No
5 0.12345 0.54321 No

Код

Решение

В основе заданной фигуры лежит круг с радиусом [latex]6[/latex] и центром в начале системы координат [latex](0, 0)[/latex], из которого исключена первая четверть. Таким образом, нам нужно удостовериться, что положение заданной точки одновременно удовлетворяет следующим условиям:

  • точка расположена в пределах круга, то есть сумма квадратов координат [latex]x^2+y^2[/latex] меньше или равна квадрату радиуса [latex]6^2=36[/latex];
  • хотя бы одна из координат точки [latex](x, y)[/latex] не превышает значения [latex]0[/latex] (другими словами, точка не лежит в первой четверти).

Если оба условия соблюдены, точка принадлежит фигуре. В противном же случае — нет. Такую проверку и последующий вывод ответа можно записать с помощью единственной тернарной операции:

Ссылки

Код программы на Ideone.com;

Уравнение окружности;

Список задач на ветвления.

Mif 17.5

Условие

Принадлежит ли точка [latex] \left( x,y \right) [/latex] фигуре на рисунке?

рисунок 17.5

Входные данные

Координаты точки [latex]\left(x,y\right)[/latex] на плоскости.

Выходные данные

Если точка принадлежит фигуре, вывести «Принадлежит» (без кавычек), в противном случае — «Не принадлежит».

Задача взята отсюда.

Тесты

x y Вывод
1 1 -1 Принадлежит
2 0 0 Принадлежит
3 0 4 Принадлежит
4 5 0 Принадлежит
5 0 4.00001 Не принадлежит
6 -3 5 Не принадлежит
7 2 3 Принадлежит

Решение

Фигура в задаче представлена в виде двух четвертей окружностей, лежащих в I и IV четвертях с радиусами [latex] R1 [/latex] и [latex] R2 [/latex] , которые равны соответственно [latex] 4 [/latex] и [latex] 5 [/latex]. Центры окружностей находятся в начале координатных осей. Сразу после ввода координат точки выполняем проверку принадлежности фигуре, а именно: координата [latex]X\ge0[/latex] ? В случае отрицательного ответа программа выведет сообщение «Не принадлежит». Одновременно со знаком [latex]X[/latex] выполняется проверка с помощью формулы, полученной из уравнения окружности: [latex]{\left(x-{X}_{c}\right)}^{2}+{\left(y-{Y}_{c}\right)}^{2}\le{R}^{2}[/latex], где [latex]X_{c}[/latex] и [latex]Y_{c}[/latex] — координаты центра окружности. Если координаты точки проходят данную проверку для соответствующего радиуса, который зависит от знака [latex]Y[/latex], то точка принадлежит фигуре, в противном случае выведется сообщение «Не принадлежит».

Код

Код на сайте ideone.com находится здесь.

 

 

Mif17.11

Задача. Принадлежит ли точка [latex](x;y)[/latex] фигуре на рисунке?
Новый текстовый документ

Тесты:

Ввод [latex](x,y)[/latex] Вывод
1 3 1 YES
2 -3 1 NO
3 -3 -1 NO
4 3 -1 YES
5 4 7 NO
6 4 -7 NO

Код программы:

Решение:

Изучив рисунок, находим координаты трех точек сегмента круга. После, находим координаты центра круга и его радиус с помощью данного сайта. Если проекция точки на ось [latex]OX[/latex] не находиться в области допустимых значений [latex]x[/latex], то точка не принадлежит сегменту круга в любом случае. Если же первое условие выполняется, то точка принадлежит сегменту круга тогда, когда квадрат расстояния ([latex]l[/latex]) от центра круга до точки меньше либо равно квадрату радиуса ([latex]r[/latex]) круга ([latex]r*r[/latex] >= [latex]l[/latex])

Условие задачи здесь.

Ссылка на решение задачи на компиляторе ideone.com здесь.

А60е

ЗадачаБезымянный

Пусть [latex]D[/latex] — заштрихованная часть плоскости (рис.) и пусть [latex]u[/latex] определяется по  [latex] x [/latex] и  [latex] y [/latex] следующим образом (запись [latex] (x, y)[/latex] [latex] \in[/latex] [latex]D [/latex] означает, что точка с координатами [latex] x ,y [/latex] принадлежит [latex] D [/latex]).
[latex]u=\left\{\begin{matrix}x+y,&\left(x,y\right)\in D\\x-y,&\left(x,y\right)\notin D\end{matrix}\right.[/latex]
Код C++

Код C++ на Ideone: www.ideone.com/s6vMul

Код Java

Код Java на Ideone: A60e

 Комментарии

 Для всех трех функций необходимо  проверить чтобы заданная ордината была больше [latex]y=x^{2}[/latex]  и одновременно меньше [latex]y=e^{-x}[/latex] , [latex]y=e^{x}[/latex].

Тесты

x y Результат Комментарий
0 0 0 Пройден
0 1 1 Пройден
34 45 -11 Пройден

А59д

Даны действительные числа [latex]x[/latex], [latex]y[/latex]. Определить, принадлежит ли точка с координатами [latex]x[/latex], [latex]y[/latex] заштрихованной части плоскости.

cpp

Тесты:

KX KY ПРИНАДЛЕЖИТ?
1 1 нет
0 0 да
0.5 0 да
0.25 0.5 да
-0.25 1.5 нет

Ссылка на код: http://ideone.com/R3DlCS

Ссылка на код: ссылка

Ход решения:

Зададим функцией [latex]f\left({x}\right)[/latex] уравнение прямой для двух точек с координатами[latex]\left(x_{0} ; y_{0}\right)[/latex] и [latex]\left(x_{1} ; y_{1}\right)[/latex], которое имеет вид:  [latex]\left( x — x_{0}\right)\cdot\left( y_{1} — y_{0}\right) — \left( y-y_{0}\right)\cdot\left( x_{1} — x_{0}\right) = 0[/latex]

Подставим нужную нам точку в уравнение каждой прямой. Если значение положительное, то точка находится со внутренней стороны. На самом деле в двух четвертях значение будет отрицательное, но для удобства я сделал так, чтобы они были тоже положительны (отнимая вершины наоборот в тех четвертях, где значение отрицательное). То есть,  если  значение во всех 4 случаях будут положительные, либо [latex]= 0[/latex] (Значение [latex]0[/latex] означает что наша точка лежит на прямой, а следовательно принадлежит фигуре)  мы можем утверждать что точка находится в  заштрихованной плоскости. В противном случае она находится вне неё.

 

А60д

Задача.

Пусть D — заштрихованная часть плоскости и пусть u определяется по и y следующим образом :

[latex]u=\begin{cases} \sqrt{|x^{2}-1|} & \text{ if } (x, y)\epsilon D \\ x+y & \end{cases}[/latex]

Даны действительные числа x и y. Определить u.
1

Тесты.

Ввод Вывод
x y u
0 0 1
0 0.5 1
-0.3 0.6 0.953939
0.3 0.6 0.953939
-0.2 -0.1 -0.3
0.8 0.6 1.4
0.5 -0.5 0

 

 

 

Решение.

Через переменные x, y обозначим координаты точки.

Мы имеем 3 графика функций:

  1. [latex]y=-x[/latex]
  2. [latex]y=x[/latex]
  3. [latex]x^{2}+y^{2}=1[/latex]

 

Проверяем находится ли точка в заштрихованной области. Точка обязательно должна находиться над или на оси x. 

Если точка принадлежит данной области то для расчёта используем формулу:

[latex]\sqrt{|x^{2}-1|}[/latex]

В противном случае формулу:

[latex]u=x+y[/latex]

 

А59з

Задача. Даны действительные числа [latex]x, y[/latex]. Определить, принадлежит ли точка с координатам [latex]x, y[/latex] заштрихованной части плоскости (рис. ниже).

ыфв

Объявляем две переменные [latex]x,y[/latex] типа [latex]double[/latex] (точки могут иметь дробные координаты). Читаем координаты точки. В условии проверяем три пункта:

  1. Лежит ли [latex]y[/latex] выше [latex]-2[/latex] [latex](y>=-2)[/latex].
  2. Находится ли точка между двумя прямыми [latex](|x|<=1)[/latex].
  3. Лежит ли точка ниже диагоналей,описанных функцией [latex]y=|x|[/latex].

Если все эти три условия соблюдены, то точка находится в закрашенной области, иначе вне этой области.

Реализация на Java:

 

 

A59б

Задача:

Для задачи (А.59(б)

Даны действительные числа

Определить, принадлежит ли точка с координатами x, y  заштрихованной области.

X  Y  Ответ
-0.65 -0.75  Yes
-0.95 -0.59 No
700 8 No
0 0 No
0.56 0.75 Yes
1,0011 1,0012 No
0.6 0 Yes

Код программы на С++

Код программы на Java

Поскольку заштрихованная область это круг с «вырезанным кругом» внутри, то для того чтобы определить лежит ли точка в нужной нам области нам достаточно сравнить сумму квадратов координат точек с квадратом радиуса двух окружностей, которые и являются нашими границами.

Если точка лежит на самой окружности, мы считаем что она принадлежит нужной нам области.

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

 

Образец: Принадлежит ли точка треугольнику?

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.

Тесты

В тестах нужно обязательно отразить следующие случаи:

  1. Точка строго вне треугольника
  2. Точка строго внутри треугольника
  3. Точка совпадает с одной из вершин треугольника
  4. Точка лежит на одной из сторон треугольника
  5. Точка лежит на продолжении одной из сторон треугольника
  6. Одна из сторон треугольника параллельна одной из осей координат
  7. Две стороны треугольника параллельны осям координат
xa ya xb yb xc yc xd yd Принадлежит?
-1 -1 1 -1 0 1 2 2 нет
-2 -2 1 -1 0 1 0 0 да
-1 -1 1 -1 0 1 0 1 да
-1 -1 1 -1 0 1 0.5 0 да
-1 -1 1 -1 0 1 1 3 нет
-1 -1 1 -1 0 1 0 0 да
0 0 2 0 0 2 1 1 да
0 0 2 0 0 2 5 5 нет

Плохое решение

В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.

Неплохое решение

Начнём с простого наблюдения:

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

Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Неважно как называть стороны, важно научиться их различать.

Неважно как называть стороны, важно научиться их различать.

Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].

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

Естественно, что нам придётся записать аналогичные условия для двух оставшихся сторон треугольника (или для всех оставшихся сторон выпуклого многоугольника).

Плохой код

Начнём с того, что объявим переменные и прочитаем их значения. После этого запишем одно очень громоздкое условие, которое и проверяет принадлежность.

Нажмите здесь, чтобы выполнить этот код.

Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.

Неплохой код

Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:

Нажмите здесь, чтобы выполнить этот код.
Трудно сказать, стал ли код боле понятным или лаконичным. Однако можно точно сказать, что в нём отсутствуют повторяющиеся алгоритмические блоки. Все участки кода написаны строго по одному разу. Это уменьшает вероятность ошибки.

Чеширский код

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать...

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…


Возможно слишком смело называть это хорошим кодом, но мы сделаем ещё один шаг в нужном направлении. В прошлом коде мы избавились от повторов в кодировании алгоритма. Однако остались повторы в кодировании данных. Вы заметили, что у нас четыре пары переменных? Т.е. просматривается структура состоящая из пары координат x и y, которую стоит объединить и назвать «точкой». Такие структуры в программировании на Си описывают с помощью ключевого слова struct. Это полезная промежуточная структура перед переходом к объектно-ориентированному программированию при помощи классов.

Нажмите здесь, чтобы выполнить этот код.
Вы заметили как забавно увеличивается размер программы по мере того, как мы пытаемся сделать его более логичным и наглядным? Это характерно для маленьких программ. Такие дополнительные структуры становятся всё более оправданными для больших и огромных программ.

А59к

Задача.

Даны действительные числа [latex]x[/latex],[latex]y[/latex]. Определить, принадлежит ли точка с координатами [latex](x;y)[/latex] заштрихованной части плоскости.

A59k

Тесты.

Ввод Вывод
[latex](-5.25;1.5)[/latex] Принадлежит
[latex](-3;1)[/latex] Принадлежит
[latex](0.6;0.6)[/latex] Принадлежит
[latex](-0.8;0.9)[/latex] Принадлежит
[latex](0.5;0.4)[/latex] Не принадлежит
[latex](-0.25;-0.3)[/latex] Не принадлежит

Код.

(C++)

Java

Решение.

Решение задачи сводится к поиску условия, при котором точка будет принадлежать данной части плоскости. В данной задаче условие будет такое: точка находиться выше прямой [latex]y=1[/latex], то есть ордината точки [latex]y\geq 1[/latex] (границы включаем) или точка находится выше графика функции [latex]y=\left|x \right|[/latex] на промежутке [latex]x[/latex]∈ [latex]\left[-1;1 \right][/latex], то есть [latex]y\geq \left|x \right|[/latex] , [latex]-1\leq x\leq 1[/latex] (границы включаем).

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++)  или другой(Java).