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;

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

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