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 Отрезки не пересекаются

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

Решение

Пусть концы отрезков имеют координаты [latex](x1,y1),[/latex] [latex](x2,y2),[/latex] [latex](x3,y3),[/latex] и [latex](x4,y4),[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=ux1+(1−u)x2; \newline y=uy1+(1−u)y2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex] $$\begin{cases}x=vx3+(1−v)x4 \newline y=vy3+(1−v)y4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex] $$\begin{cases}ux1+(1−u)x2=vx3+(1−v)x4 \newline uy1+(1−u)y2=vy3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y4-y3)\cdot(x1-x2)-(x4-x3)\cdot(y1-y2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x4-x2)\cdot(y4-y3)-(x4-x3)\cdot(y4-y2)}{denominator} \newline Ub=\frac{(x1−x2)\cdot(y4−y2)−(x4−x2)\cdot(y1−y2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone

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.16

Молоканов Юрий
Молоканов Юрий

Latest posts by Молоканов Юрий (see all)

Условие

Принадлежит ли точка [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 находится здесь.

 

 

А59д

Стеблинський Ігор Віталійович
Стеблинський Ігор Віталійович

Latest posts by Стеблинський Ігор Віталійович (see all)

Даны действительные числа [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д

Ковальський Олександр Дмитрович
Ковальський Олександр Дмитрович

Latest posts by Ковальський Олександр Дмитрович (see all)

Задача.

Пусть 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]