e-olymp 7504. Три прямоугольника

Задача взята с сайта e-olymp

Задача

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

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

Одно число — количество закрашенных клеток

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

В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 0 1 1
1 1 2 2
0 0 2 2
4
2 2 -2 -2 2
-1 -1 1 1
40 40 41 41
17
3 -1 2 2 -1
1 0 4 2
1 0 3 6
21
4 -100 -100 -99 -99
100 100 99 99
-100 -100 100 100
40000
5 3 0 4 1
1 0 3 3
1 0 3 3
7

Решение

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

Для нахождения пересечения прямоугольников рассмотрим проекции координат прямоугольника на координатные оси $x$ и $y$. В случае, если интервалы пересекаются, началом пересечения будет наибольшее из начал интервалов, а концом —  наименьшее из их концов. В ином же случае дадим точкам по этой координате одинаковые значения, в результате чего площадь такого прямоугольника и всех пересечений, которые он образует будет равна нулю. Координатами точек пересечения прямоугольников будут, следовательно, соответствующие координаты пересечения интервалов на осях.

После этого задача сводится к написанию функции общей площади. То, что решение, в котором мы просто суммируем площадь трех прямоугольников проходит лишь на один тест, наводит на мысль о том, что мы добавляем площадь пересечений несколько раз. Следовательно, от суммы площадей трех прямоугольников отнимем площадь их пересечения друг с другом и добавим площадь пересечения всех трех(поскольку в случае, если существует пересечение трех, то мы лишний раз отнимаем его площадь).

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

Решение. Многомерные массивы

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

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

e-olymp 4557. Одинокий король

Задача взята с сайта e-olymp.

Задача


Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [latex] n [/latex] ходов.

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

В первой строке задано общее число ходов короля [latex] n [/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex] n [/latex] строках заданы направления перемещения короля: строка под номером [latex] i + 1 [/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

# Входные  данные Выходные данные
1 5 1 2 4 7 4 4
2 5 1 2 4 6 4 Ok 2
3 3 1 2 1 Ok 5
4 3 1 5 1 2
5 8 8 8 8 8 8 8 8 8 Ok 8

Код

Решение

За изначальное местоположение короля возьмем точку с координатами [latex](0, 0)[/latex], а все передвижения короля по шахматной доске — это изменение абсциссы и (или) ординаты данной точки. Создадим два динамических массива  x = new int [n];  и  y = new int [n]; на [latex] n [/latex] элементов каждый, для абсцисс и ординат соответственно. Они будут хранить изменения координат всех точек, в которых побывал король. При этом, так как мы считаем, что начинаем движение с начала координат начнем заполнение массивов со второго элемента. Когда массивы в цикле  for (int i = 1; i <= n; i ++);  заполнятся будем искать совпадающие точки в другом цикле, если же таких не найдется, посчитаем расстояние между конечным и начальным местоположением короля, однако так как начальное местоположение короля — это начало координат, то ограничимся лишь немного упрощенной формулой [latex]d = |x_n| + |y_n|[/latex], или же в коде это выглядит так:  abs(x[n]) + abs(y[n]);. После, не забываем удалить уже использованные массивы, чтобы освободить память.

Код 2

Решение 2

Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы  if(); можно заменить массивами  X[]; и  Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.

Код 3

Решение 3

Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор  switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.

Ссылки

  • Засчитанное решение 1 на e-olymp.
  • Засчитанное решение 2 на e-olymp.
  • Засчитанное решение 3 на e-olymp.
  • Код 1 в ideone.
  • Код 2 в ideone.
  • Код 3 в ideone.

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

e-olymp 72. Дорога домой

Задача

Бедный Иа

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]left langle 1,1 right rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.

Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]left langle 0,0 right rangle[/latex], а его дом расположен в точке [latex]left langle x_{h},y_{h} right rangle[/latex], и направление движения он менял [latex]k[/latex] раз.

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

В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0leq n,k,t,vleq 100)[/latex]
. Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5leq x_{h}, y_{h}leq 10^5)[/latex]
.

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

Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.

Тесты

Входные данные
Выходные данные
[latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex]

 

[latex]5[/latex] [latex]7[/latex]

Good night Ia
[latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex]

 

[latex]15[/latex] [latex]15[/latex]

Good night Ia
[latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex]

 

[latex]105[/latex] [latex]-105[/latex]

Poor Ia
[latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex]

 

[latex]40[/latex] [latex]-20[/latex]

Good night Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]

 

[latex]-24[/latex] [latex]0[/latex]

Poor Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]

 

[latex]-23[/latex] [latex]0[/latex]

Good night Ia

Первый вариант кода программы

Второй вариант кода программы

Решение задачи

Вариант 1

Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]sumlimits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:

[latex]f(x,y) = begin{cases} left langle1 + xy, 1 + xyright rangle & textit{if } xvdots 4 = 0 \ left langle1 + xy, (-1) cdot (1 + xy)right rangle & textit{if } xvdots 4 = 1 \ left langle(-1) cdot (1 + xy), (-1) \cdot (1 + xy)right rangle & textit{if } xvdots 4 = 2 \ left langle(-1) cdot (1 + xy), 1 + xyright rangle & textit{if } xvdots 4 = 3 end{cases}[/latex]

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]sumlimits_{i=0}^k f(i, n)[/latex] — это вектор [latex]left langle a,b right rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]left langle a,b right rangle[/latex] и вектора [latex]left langle x_{h},y_{h} right rangle[/latex]:

$$sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$

И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]left langle 0,0 right rangle[/latex] и [latex]left langle 1,1 right rangle[/latex], то есть — [latex]sqrt{2}[/latex].

$$ sqrt{2} tv$$

Итого, выводим Good night Ia, если [latex]2t^2v^2 geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.

Вариант 2

Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = displaystylefrac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$

Для направления на северо-восток:
$$a_1 = 1, d = 4n Rightarrow S_{1}=frac{1 + 1 +4n(m_1-1)}{2}Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=1$ иначе, $m_1=displaystylefrac{k+1}{4}$

Для направления на юго-восток:
$$a_2 = 1+n, d = 4n Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=2$ иначе, $m_2=displaystylefrac{k+1}{4}$

Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=3$ иначе, $m_3=displaystylefrac{k+1}{4}$

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=4$ иначе, $m_4=displaystylefrac{k+1}{4}$

Тогда, для вычисления координат [latex]left langle x,y right rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.

Ссылки

Условие задачи на e-olymp
Код решения первого варианта на ideone.com
Код решения второго варианта на ideone.com

There is no Spoon — Episode 1

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

  • You give an incorrect neighbor for a node.
  • You give the neighbors for an empty cell.
  • You compute the same node twice.
  • You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3
Where:

  • ( x1, y1) the coordinates of a node.
  • ( x2, y2) the coordinates the closest neighbor on the right of the node.
  • ( x3, y3) the coordinates the closest bottom neighbor.

[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input Output
2 2
00
0.
0 0 1 0 0 1
1 0 -1 -1 -1 -1
0 1 -1 -1 -1 -1
4 4
.0..
.000
000.
..0.
1 0 -1 -1 1 1
1 1 2 1 1 2
2 1 3 1 2 2
3 1 -1 -1 -1 -1
0 2 1 2 -1 -1
1 2 2 2 -1 -1
2 2 -1 -1 2 3
2 3 -1 -1 -1 -1

The code of the program

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Площадь поверхности

Задача

Найти площадь поверхности, которая является трёхмерным графиком функции [latex]f\left( x, y\right)[/latex], в пределах от [latex]a[/latex] до [latex]b[/latex] по оси [latex]x[/latex] и от [latex]c[/latex] до [latex]d[/latex] по оси [latex]y[/latex] c величиной шага [latex]h[/latex].

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

Четыре целых числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex].
Вещественное число: [latex]h[/latex].

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

Площадь поверхности [latex]S[/latex].

Тесты

 № [latex]f\left( x, y\right)[/latex] Входные данные Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex]  [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1  [latex]x+y[/latex]  -10  10  -10  10  0.001  692.82
 2  [latex]\left| x \right| +\left| y \right|[/latex]  -2  2  -2  2  0.005  27.7128
 3  [latex]1[/latex]  0  100  0  100  0.1  10000
 4  [latex]{x}^{2}+{y}^{2}[/latex]  -1  1  -1  1  0.0005  7.44626

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

Решение

Представим поверхность в виде множества геометрических фигур. Тогда её площадь будет суммой площадей этих фигур. В качестве фигур, покрывающих данную поверхность, возьмём треугольники, поскольку через любые [latex]3[/latex] точки в пространстве можно провести плоскость и только одну (а значит и треугольник). Координатную плоскость [latex]xy[/latex] условно поделим на квадраты, где сторона квадрата будет равняться заданному шагу [latex]h[/latex]. Будем рассматривать только квадраты, что лежат в заданных пределах.  Условно проведём одну из диагоналей у каждого квадрата — получим треугольники на плоскости. Поочередно будем искать координату [latex]z[/latex] вершин каждой пары треугольников, подставляя уже известные координаты [latex]x[/latex] и [latex]y[/latex] в указанную формулу. Зная координаты треугольников в пространстве, найдём площадь каждого, сумма данных площадей и будет площадью поверхности. Чтоб найти площадь треугольника, зная координаты его вершин, найдем векторное произведение его координат. Возьмем треугольник с координатами вершин  [latex]\left( x_i,y_i,z_{ii} \right) [/latex], [latex]\left( x_i, y_j, z_{ij} \right) [/latex] и [latex]\left( x_j, y_i, z_{ji} \right) [/latex], возьмём произвольные два вектора, которые образуют данный треугольник — [latex]\overrightarrow { a } =\left ( x_i-x_i, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, y_i-y_i, z_{ji}-z_{ii} \right)[/latex].
[latex]\overrightarrow { a } =\left ( 0, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, 0, z_{ji}-z_{ii} \right)[/latex].
Тогда векторное произведение [latex]\left [ \overrightarrow { a }, \overrightarrow { b } \right] =\left ( (y_i-y_j)( z_{ji}-z_{ii}), (z_{ii}-z_{ij})(z_{ji}-z_{ii} ), ( y_j-y_i)(x_j-x_i) \right)[/latex].
Поскольку длина вектора равного векторному произведения двух векторов в пространстве равна площади параллелограмма, образованного исходными векторами — найдём его длину и разделим пополам, чтоб получить площадь треугольника, образованного исходными векторами. Значит площадь каждого треугольника можно вычислить по формуле:
[latex]s =\frac { 1 }{ 2 } \sqrt{({(y_i-y_j)}^{2}{( z_{ji}-z_{ii})}^{2}+{(z_{ii}-z_{ij})}^{2}{(z_{ji}-z_{ii} )}^{2}+{( y_j-y_i)}^{2}{(x_j-x_i)}^{2})}[/latex]
Тогда площадь поверхности в пределах заданных точек можно вычислить, сложив площади этих треугольников.

Модификация

Модифицируем данную программу для нахождения приблизительной площади поверхности, заданной функцией с корнем чётной степени.

Тесты

 № [latex]f\left( x, y\right)[/latex] [latex]z_0[/latex]  Входные данные  Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex] [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]1[/latex]  -1  1  -1  1  0.00011  6.28734
 2 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]7y[/latex]  -1  1  -1  1  0.00011  23.0803
 3 [latex]\sqrt { 1-{ x }^{ 2 }-\frac{ { y }^{ 2 }}{ 2 } }[/latex] [latex]0[/latex]  -1  1  -2  2  0.00015  8.08214
 4 [latex]\sqrt { 2-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]-1[/latex]  -2  2  -2  2  0.0005  12.5835

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

Условно отделим от функцию [latex]f\left( x, y\right)[/latex] слагаемые, что не под корнем, если такие имеются. Тогда [latex]z_0[/latex] равно части функции, что не под корнем. Для того, чтоб рассматривать площади треугольников, вершины которых выходят за область определения функции, доопределим их в [latex]z_0[/latex] по оси [latex]z[/latex]. Затем вычислим площадь треугольников, у которых как минимум одна вершина не лежит на [latex]z=z_0[/latex] .

Ссылки

A60г

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть u определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом: [latex] u=\begin{cases}x^{2}-1, ; \text{ if } (x, y)\in D \\sqrt{\left| x-1 \right| } ; \text{ another case }\end{cases}[/latex] (запись [latex] (x, y)\in D [/latex] означает, что точка с координатами [latex]x, y[/latex] принадлежит [latex]D[/latex]).

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

a60%d0%b3
Тесты:

Вход Выход
[latex]x[/latex] [latex]y[/latex] [latex]u[/latex]
1 0.3 0.3 0.836660
2 1 1 0.000000
3 2 2 1.000000
4 0 0 -1.000000

Код на языке C++:

Код на языке Java:

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex] y<0 [/latex].Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3 .
Ссылки:
Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .

Mif 17.14

Задача.

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

Задача взята здесь.

Трапеция

Тесты

[latex]x[/latex] [latex] y[/latex] Ответ
-2 4 Принадлежит
4 8
Не принадлежит
-7 9
Не принадлежит
0 0
Не принадлежит
0 1
Принадлежит
4 1
Принадлежит
-7 1  Принадлежит

Код

Решение

Каждая из сторон тарпеции делит плоскость на 2 части. Сторона имеет вид [latex]y = k*x + b[/latex]. Путем подстановки были найдены коефициенты [latex] k [/latex] и [latex] b [/latex].  Точка может лежать либо ниже, либо выше, либо на стороне. Если [latex]y — k*x <= b[/latex], точка лежит на или ниже стороны. Основы трапеции представлены в виде [latex] y =1 [/latex] и [latex] y = 7 [/latex].

Ссылка на ideone.com

Mif 17.7

Задача.

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

Новый текстовый документ1

Тесты:

[latex]x[/latex] [latex]y[/latex] Результат
 -6  3 принадлежит
 0 0  не принадлежит
 2 -4  не принадлежит
 — 1 2 принадлежит
 -5 -2  принадлежит

 

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

Решение.

В данной задаче необходимо проверить подходят ли координаты точки под условия, описывающие фигуру. В этом варианте фигуру можно разбить на 2 прямоугольника. Тогда вышеуказанные условия выглядит так: [latex]-6<=x<=-1[/latex] и [latex]2<=y<=7[/latex] (это первый прямоугольник) или [latex]-6<=x<=-3[/latex] и [latex]-3<=y<=2[/latex] (соответственно, второй прямоугольник).

Здесь находится условие задачи

Ссылка на код на ideone.com

Mif 17.17

Условие :

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

Рисунок :

picture

Тесты :

[latex]x[/latex] 4 -5 0 3 -2.5 1 -3 2 -1.3
[latex]y[/latex] 3 0 -5 -2 -2.5 5 3 -4 2.7
Вывод : Yes Yes Yes Yes Yes No No No Yes

Решение :

Во [latex]II[/latex], [latex]III[/latex] и [latex]IV[/latex] координатных четвертях данная фигура удовлетворяет неравенству [latex]|x| + |y| \leq 5[/latex], а в [latex]IV[/latex] — неравенству [latex]x^2 + y^2 \leq 25[/latex]. Программа должна проверять, подходят ли числа [latex]x[/latex] и [latex]y[/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».

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

 

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

Ю2.15

Задача.  Общая точка

Два отрезка на плоскости заданы координатами своих концов. Определить имеют ли эти отрезки общие точки.

Замечание. Необходимо рассмотреть различные случаи взаимной ориентации отрезков: на одной прямой, на параллельных или пересекающихся прямых. Тестирование должно предусмотреть все такие ситуации.

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

Координаты концов двух отрезков [latex]AB, CD [/latex]  в формате [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] ([latex]x_i, y_i[/latex] — действительные числа).

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

Расположение отрезков, а именно:

  • «Intersect at point [latex](x, y)[/latex]»
  • «Don’t intersect» 
  • «Paralell» 
  • «On the same line, but don’t intersect»
  • «Overlap»  (Находятся на одной прямой и хотя бы одна из точек совпадает)

Тесты

 Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]   Расположение отрезков
1 1 5 4 1 3 5 3 Intersect at point (3.66667, 3)
-7 2 -4 2 -6 3 -3 3 Paralell
1 2 3 2 2 2 6 2 Overlap
1 2 4 2 5 2 7 2 On the same line, but don’t intersect
1 2 4 4 2 1 5 3 Paralell
1 1 4 2 7 3 10 4 On the same line, but don’t intersect
1 1 5 3 5 3 7 4 Overlap
1 1 5 4 1 4 5 2 Intersect at point (3.4, 2.8)
1 1 2 4 3 2 6 4 Don’t intersect

 

 Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]   Расположение отрезков
1 1 1 5 3 2 3 4 Paralell
1 2 4 5 2 2 2 5 Intersect at point (2, 3)
2 1 2 2 2 4 2 6 On the same line, but don’t intersect
2 1 2 5 1 2 4 2 Intersect at point (2, 2)
1 2 4 2 2 3 2 5 Don’t intersect

 

Алгоритм решения

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

  1. areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
    ( Основная формула:  [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] )
  2. getMin — возвращает минимум двух чисел.
  3. getMax —  возвращает максимум двух чисел.
  4. projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
  5. getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] )
  6. getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] )
  7. getCos — функция, принимающая координаты двух векторов и возвращающая косинус угла между ними.
    ( Основная формула:  [latex]\frac{x_1x_2 + y_1y_2}{\sqrt(x_1^2 + y_1^2) + \sqrt(x_2^2 + y_2^2)}[/latex] )

Перейдем к основной части программы. Сразу следует оговорить, что последующее решение будет базироваться на векторах и работе с уравнением прямой вида [latex] y = kx + b [/latex], поэтому для удобства отдельно заведем переменные для координат векторов соответствующих отрезкам и значений вычисленных коэффициентов и свободных членов уравнений прямых.  Одной из главных проблем на пути решения стали отрезки располагающиеся на прямых вида [latex]x = a [/latex], ведь если обратится к пунктам 5, 6 можно заметить, что в таких случаях мы получим исключение из-за деления на ноль. Этим вызвано вынужденное разделение программы на два блока — где ни один из отрезков не располагается параллельно оси ординат и когда хотя бы один из них параллелен.  Это удается достичь благодаря инициализации логических переменных, принимающих значение true, когда отрезок расположен на прямой [latex]x = a[/latex]. Также изначально подсчитываем значения переменных yIntercept1, yIntercept2, slope1, slope2 тогда, когда это возможно, так как они будут задействованы в дальнейшем.

Теперь мы можем приступить к общему рассмотрению сложившейся ситуации, когда прямые параллельные оси ординат отсутствуют:

  1. Решим систему уравнений для двух заданных прямых и таким образом найдем точку их пересечения.
    [latex] \left\{\begin{matrix}
    k_1x + b_1 = y & \\
    k_2x + b_2 = y &
    \end{matrix}\right.[/latex]
  2. Найдя точку с координатами [latex](xIntersection,yIntersection)[/latex], следующим шагом станет проверка : принадлежит ли найденная точка имеющимся отрезкам. Для этого воспользуемся формулой скалярного произведения и определим косинус угла между векторами с началом в точке [latex](xIntersection, yIntersection)[/latex] и концами в соответствующих концах отрезка. Выполняем ее для двух отрезков. Если в обоих случаях найденный косинус будет [latex] \le[/latex] [latex]0[/latex], то точка находится на двух отрезках одновременно и  является их пересечением. Выводим сообщение «Intersect at point [latex](xIntersection, yIntersection)[/latex]«.
  3. В случае, если такая точка не найдена в следствие определенных причин, рассмотрим следующие возможные ситуации:
    а) При условии, что равны свободные члены уравнения прямых и точка не была найдена, можем проверить утверждение, что рассматриваемые прямые совпадают, а заданные отрезки находятся на ней. Здесь требуют рассмотрения  два варианта: отрезки накладываются, если проекции отрезков на ось абсцисс накладываются друг на друга, или же отрезки находятся на одной прямой и не пересекаются. Выводим соответствующее сообщение : «Overlap»/»On the same line, but don’t intersect».
    б) 
    Если свободные члены не равны и не выполнилось ни одно из предыдущих утверждений, приходим к выводу, что возможно отрезки, которые задают вектора, параллельны. Выполняем проверку на коллинеарность , в случае подтверждения предположения выводим сообщение : «Parallel».
    в) 
    Пройдя через все вышеупомянутые проверки и не получив логического значения true, определяем, что данные отрезки не пересекаются и не удовлетворяют ни одному из особенных случаев. Выводим сообщение : «Don’t intersect».Таким образом рассмотрение общего случая окончено. Перейдем ко второй ситуации:
  1. Если оба отрезка расположены на прямых вида [latex]x = a[/latex], то имеем следующие варианты:
    а) Если отрезки расположены на одной прямой и их проекции на ось ординат пересекаются, выводим сообщение : «Overlap».
    б) 
    Если отрезки расположены на одной прямой и их проекции на ось ординат не пересекаются, выводим сообщение : «On the same line, but don’t intersect».
    в) Если отрезки расположены не на одной прямой, выводим сообщение «Paralell».
  2. При условии, что только одна из прямых имеет вид [latex]x = a[/latex], рассмотрим следующие ситуации:
    а)Только одна из прямых имеет вид [latex]x = a[/latex] и обе имеют коэффициент угла наклона равный [latex]0[/latex]. Перед нами две прямые вида: [latex] y = b[/latex] и  [latex]x = a [/latex]. Выполняем смену между соответствующими координатами, чтобы не дублировать код для двух аналогичных ситуаций и рассматриваем только одну из них. Нетрудно заметить, что единственным решением является точка [latex](x_3/x_4, y_1/y_2)[/latex] . Используя метод getCos, выполняем уже описанную выше проверку на принадлежность точки отрезку. Если да — выводим сообщение : «Intersect at point [latex](x_3, y_1)[/latex]», в противном случае : «Don’t intersect».
    б) Однако, ни одна из предыдущих проверок могла не выполниться, так как существует еще одно расположение отрезков на прямых [latex] y = kx + b [/latex] и [latex]x = a [/latex]. Выполняем аналогичную операцию по смене координат во избежание дублирования кода. Единственным решением данной системы может являться точка [latex](x3/x4 + yIntercept1, x3/x4)[/latex]. Повторяем операции аналогичные последним из пункта б). Выводим сообщение: «Intersect at point [latex](x3 + yIntercept1, x3)[/latex]» или «Don’t intersect».
    (В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).

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

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

Аналогичная задача на сайте e-olymp:
839. Пересечение отрезков (Засчитанное решение)

Mif 17.2

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

4

Решение

Данный рисунок находится в I и IV четверти, следовательно [latex] x [/latex] может быть только положительным, а [latex] y [/latex], как положительным, так и отрицательным. На рисунке нам даны две окружности. Одна с центром в точке (-0.5;0) и радиусом 3, а другая (0;0) и радиусом 5. Нам нужно, чтобы наша точка находилась только в первой и четвертой четвертях и при этом, чтоб выходила за пределы первой окружности, и чтоб не выходила за предел второй окружности. Для того, чтобы узнать принадлежит ли точка данной фигуре нужно подставить значения и проверить будут ли они принадлежать рисунку с помощью уравнений двух окружностей и описанных выше условий.

Уравнение окружности выглядит так: \left(x-a \right)^2+\left(y-b \right)^2=R^2. Подставим значения центров окружностей и получим, что для первой окружности уравнение имеет вид:[latex](x+0.5)^{2}+y^{2}=3^{2}[/latex], а для второй: [latex] x^{2}+y^{2}=5^{2}[/latex].

Код

 

Тесты

Входные данные Выходные данные
4 5  no
1 2  no
2 -2  yes

Задача взята отсюда.
Код программы на Ideone.com.

 

e-olymp 918. Какая четверть?

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

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

В единственной строке через пробел заданы [latex]2[/latex] вещественных числа — координаты точки, значения координат по модулю не превышают [latex]100[/latex].

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

Единственное число — номер соответствующей четверти, либо [latex]0[/latex], если однозначно определить четверть невозможно.»

Ссылка на код на ideone.
Ссылка на засчитанное решение.

Тесты

[latex]x[/latex] [latex]y[/latex] четверть [latex]x[/latex] [latex]y[/latex] четверть
2 -2 4 0 54 0
5 7 1 -3 4 2
-3 0 0 -3 -8 3
0 0 0

Поскольку в любом случае мы обращаемся к оператору вывода, имеет смысл вложить условия в этот оператор.  Сначала мы проверяем, не равна ли хотя бы одна переменная нулю. Если да — выводим [latex] 0[/latex], если нет — проверяем, больше ли [latex]x[/latex] нуля. Если да — это будет первая или четвертая четверть, если нет — вторая или третья. Внутри проверки [latex]x[/latex] проверяем [latex]y[/latex]. Если y больше нуля — это первая или вторая четверть, если меньше — вторая или третья.

А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] означает что наша точка лежит на прямой, а следовательно принадлежит фигуре)  мы можем утверждать что точка находится в  заштрихованной плоскости. В противном случае она находится вне неё.

 

А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).

А52

Задача. Даны действительный числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex], [latex]s[/latex], [latex]t[/latex], [latex]u[/latex]([latex]s[/latex] и [latex]t[/latex] одновременно не равны нулю). Известно, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] не лежат на прямой [latex]l[/latex], заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] разбивает координатную плоскость на две полуплоскости. Выяснить, верно ли, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] принадлежат разным полуплоскостям.

В этой задаче надо воспользоваться тем, что две точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на прямой, определяемой уравнением [latex]sx + ty + u = 0[/latex], принадлежат одной полуплоскости, если [latex]sa + tb + u[/latex] и [latex]sc + td + u[/latex] – числа одного знака. Справедлив и более общий факт: если уравнение [latex]F(x, y) = 0[/latex] определяет прямую или кривую, разбивающую координатную плоскость на две части, то точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на этой линии, принадлежат одной и той же части плоскости, если [latex]F(a, b)[/latex] и [latex]F(c, d)[/latex]– числа одного знака.

a b c d s t u Ответ
5 -4 2 9 6 -3 7  Обе точки принадлежат разным полуплоскостям.
-5 -4 -6 -3 2 7 -1 Обе точки принадлежат одной полуплоскости.
 -5 -4 -6 -3 0 0 -1  Условие некорректно:s и t не должны одновременно равняются нулю.
 4 7 2 1 -4 3  -5  Одна, либо обе из точек лежат на прямой, соответственно не принадлежат ни одной из полуплоскостей.

В программу вводятся исходные данные, среди которых координаты точек [latex](a, b)[/latex] и [latex](c, d)[/latex]. Если набор значений будет таким, что выполнится уравнение прямой [latex]sx+ty+u=0[/latex], (где xa и d. А yb и d), то это значит, что одни из точек (или сразу две) принадлежат прямой и следовательно не принадлежат ни одной из полуплоскостей. Если результаты уравнений [latex](s*a)+(t*b)+u[/latex] и [latex](s*c)+(t*d)+u[/latex]- числа одного знака, то точки лежат в одной полуплоскости. Если же эти числа разного знака, то обе точки принадлежат разным полуплоскостям.

Код на C++:

Код на Java:

 

С программой можно ознакомится тут (C++)/тут (Java).

Ю1.27

Задача: Треугольник задаётся координатами своих вершин на плоскости: [latex]A\left(x_{1};y_{1} \right), B\left(x_{2};y_{2} \right), C\left(x_{3};y_{3} \right)[/latex] . Найти точку [latex]D[/latex], симметричную точке [latex]A[/latex] относительно стороны [latex]BC[/latex].

[latex]a_{x}[/latex] [latex]a_{y}[/latex] [latex]b_{x}[/latex] [latex]b_{y}[/latex] [latex]c_{x}[/latex] [latex]c_{y}[/latex] [latex]d_{x}[/latex] [latex]d_{y}[/latex]
2 2 0 0 1 0 2 -2
-4 5 -2 3 -2 2 0 5
-3 -3 -4 -1 -1 -4 -2 -2
5 2 3.5 1 4.5 4 2.9 2.7

C++:

Java:

Для всех переменных ([latex]a_{x}[/latex], [latex]a_{y}[/latex], [latex]b_{x}[/latex], [latex]b_{y}[/latex], [latex]c_{x}[/latex], [latex]c_{y}[/latex] — координаты точек [latex]A, B, C[/latex], даны по условию; [latex]d_{x}[/latex], [latex]d_{y}[/latex] — координаты точки [latex]D[/latex] — нужно найти) я использовала тип double, так как они могут быть вещественными числами.

Найдём уравнение прямой [latex]BC[/latex] по формуле [latex]\frac{\left(x-x_{1} \right)}{\left(x_{2}-x_{1} \right)}=\frac{\left(y-y_{1} \right)}{\left(y_{2}-y_{1} \right)}[/latex]. Подставляем значения: [latex]\frac{\left(x-b_{x} \right)}{\left(c_{x}-b_{x} \right)}=\frac{\left(y-b_{y} \right)}{\left(c_{y}-b_{y} \right)}[/latex]. Приводим к виду: [latex]x\left(c_{y}-b_{y} \right)-y\left(c_{x}-b_{x} \right)+b_{y}\left(c_{x}-b_{x} \right)-b_{x}\left(c_{y}-b_{y} \right)=0[/latex].
Переменными [latex]A_{1}[/latex],  [latex]B_{1}[/latex],  [latex]C_{1}[/latex]  я обозначила постоянные при [latex]x, y[/latex] и свободный член, чтобы уравнение приняло вид: [latex]A_{1}\cdot x+B_{1}\cdot y+C_{1}=0[/latex].

Проведём прямую через точку [latex]A[/latex] перпендикулярно прямой [latex]BC[/latex]. Составим её уравнение по формуле: [latex]A\left(y-a_{y} \right)-B\left(x-a_{x} \right)=0[/latex]. Получим: [latex]A_{1}\cdot y-B_{1}\cdot x+B_{1}\cdot a_{x}-A_{1}\cdot a_{x}=0[/latex].  Аналогично для постоянных в этом уравнении я использовала переменные [latex]A_{2}[/latex],  [latex]B_{2}[/latex],  [latex]C_{2}[/latex]. Соответственно, [latex]A_{2}=-B_{1}[/latex],   [latex]B_{2}=A_{1}[/latex],   [latex]C_{2}=B_{1}\cdot a_{x}-A_{1}\cdot a_{y}[/latex].

Теперь найдём точку пересечения этой прямой и прямой  [latex]BC[/latex] — точку [latex]O\left(o_{x};o_{y} \right)[/latex]. Получим: [latex]o_{x}=\frac{B_{1}\cdot C_{2}-B_{2}\cdot C_{1}}{A_{1}\cdot B_{2}-A_{2}\cdot B_{1}}[/latex]   и   [latex]o_{y}=\frac{C_{1}\cdot A_{2}-C_{2}\cdot A_{1}}{A_{1}\cdot B_{2}-A_{2}\cdot B_{1}}[/latex].

Так как точка [latex]D[/latex] симметрична точке [latex]A[/latex] относительно [latex]BC[/latex], и [latex]AD[/latex] пересекается с [latex]BC[/latex] в точке [latex]O[/latex]: точка [latex]O[/latex] — середина [latex]AD[/latex]. Из формулы координаты середины отрезка (  [latex]o_{x}=\frac{a_{x}+d_{x}}{2}[/latex] и [latex]o_{y}=\frac{a_{y}+d_{y}}{2}[/latex]  ) находим [latex]d_{x}=2\cdot o_{x}-a_{x}[/latex]  и  [latex]d_{y}=2\cdot o_{y}-a_{y}[/latex].

Задача на Ideone:
C++
Java

А60б

Задача:  Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть [latex]u[/latex] определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом ( запись [latex](x, y)\epsilon D[/latex] означает, что точка с координатами [latex]x[/latex], [latex]y[/latex] принадлежит [latex]D[/latex]):

[latex]u=\left\{\begin{matrix}-3, \text{if} (x, y)\epsilon D\\ y^{2} \end{matrix}\right.[/latex]

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

Код на С++:

 

Тесты:

[latex]x[/latex] [latex]y[/latex] Результат

[latex]u[/latex]

[latex]0[/latex] [latex]0[/latex] [latex]-3[/latex]
[latex]0[/latex] [latex]1[/latex] [latex]1. 00[/latex]
[latex]1[/latex] [latex]0[/latex] [latex]-3[/latex]
[latex]-1[/latex] [latex]0[/latex] [latex]0. 00[/latex]
[latex]0[/latex] [latex]-1[/latex] [latex]-3[/latex]
[latex]0,6[/latex] [latex]0,8[/latex] [latex]0. 64[/latex]
[latex]0,5[/latex] [latex]-0,5[/latex] [latex]-3[/latex]

 

Код на Java:

 

 

Безымянный

Для того, чтобы определить находится ли нужная точка с координатами [latex](x,y)[/latex] в заштрихованной части графика, нужно задать такое условие, чтобы эта точка находилась в круге [latex]x^{2}+y^{2}=1[/latex] и была ниже прямой [latex]y=\frac{x}{2}[/latex].

Отсюда следует, что если [latex]x^{2}+y^{2}\leqslant1[/latex] и [latex]y\leqslant\frac{x}{2}[/latex], то точка принадлежит заштрихованной части круга.

Результат [latex]u[/latex] выводится с точностью до двух знаков после запятой.

Запустить код и проверить тесты можно тут: http://ideone.com/N3UoQ7.

А59е

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

A59е

Значение  [latex]x[/latex] Значение [latex]y[/latex] Комментарий
0 0 Принадлежит фигуре.
-2 0 Принадлежит фигуре.
0 1 Принадлежит фигуре.
1 0 Принадлежит фигуре.
0 -1 Принадлежит фигуре.
-2 1 Не принадлежит фигуре.
-2 -0.5 Принадлежит фигуре.
1 -1 Не принадлежит фигуре.
0.5 0.5 Принадлежит фигуре.

С++:

Java:

Если точка [latex]D[/latex] лежит справа от оси [latex]OY[/latex], ищем расстояние от неё до точки [latex]O\left(0,0 \right)[/latex]. Если оно меньше либо равно [latex]1[/latex], точка [latex]D[/latex] принадлежит полукругу.

Если точка [latex]D[/latex] лежит слева от оси [latex]OY[/latex], будем проводить прямые через каждые две вершины треугольника [latex]ABC[/latex], где [latex]A\left(-2,0 \right)[/latex], [latex]B\left(0,1 \right)[/latex], [latex]C\left(1,0 \right)[/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]

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

Функция dotLine определяет положение точки относительно прямой: она вычисляет значение в уравнении прямой и определяет, к какой части плоскости относится точка.

Для того, чтобы точка [latex]D[/latex] принадлежала треугольнику, она должна с каждой вершиной треугольника находиться по одну сторону от прямой, проходящей через две другие вершины.

Функция dotDot определяет, расположены ли точки в одной части плоскости.

Если уравнение прямой даст 0, то точка [latex]D[/latex] лежит на прямой и принадлежит треугольнику.

Задача на Ideone:
C++
Java