e-olymp 48. Красные и синие квадраты

Задача

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

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

В первой строке находится количество синих квадратов $n$ ($0 < n < 40404$). Далее идут $n$ строк, каждая из которых содержит координаты $x$, $y$ ($-101 \leq x, y \leq 101$) левых нижних углов синих квадратов.

Каждый синий квадрат имеет хотя бы одну общую точку хотя бы с одним другим синим квадратом. Фигура, образованная синими квадратами, является связной.

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

Вывести количество красных квадратов.

Тесты

Входные данные
Выходные данные
$3$
$1$ $2$
$2$ $1$
$3$ $1$
$3$
$3$
$1$ $1$
$2$ $2$
$1$ $3$
$6$
$10$
$1$ $1$
$2$ $2$
$1$ $3$
$2$ $4$
$1$ $5$
$2$ $6$
$1$ $7$
$2$ $8$
$1$ $9$
$2$ $10$
$90$

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

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

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

Чтобы доказать это, пусть сторона квадрата равна $1$. Тогда периметр фигуры, составленной из этих квадратов, всегда будет делится на $2$ (это легко понять, строя такие фигуры на листке бумаги: добавление каждого нового квадрата в фигуру может изменить периметр только на $-4, -2, 0, 2, 4$). А так как периметр прямоугольника равен $2 * (a + b)$, где $a, b$ – стороны прямоугольника, то для существования прямоугольника с таким-же периметром должно выполняться условие $\forall p \in \mathbb{N} , p > 2 \rightarrow \exists a,b \in \mathbb{N} : 2p = 2*( a + b )$. Очевидно, что условие действительно выполняется для всех $p>2$.

Запишем нашу фигуру в массив squares. После чего посчитаем ее периметр: каждый непустой квадратик фигуры добавляет $1$ к периметру за каждую пустую клеточку слева, справа, сверху или снизу от него. Далее будем искать все подходящие прямоугольники, записывая максимальную площадь в переменную max: перебирая значения первой стороны $j$, высчитываем через периметр вторую сторону $i = \displaystyle \frac{p}{2} — j$. Площадь будем считать, как разницу площади прямоугольника и изначальной фигуры (число $n$ равно площади фигуры, потому что площадь каждого квадрата равна $1$).
В конце, выводим разницу максимальной площади и площади изначальной фигуры (площадь изначальной фигуры равна $n$, ведь площадь каждого квадрата равна $1$).

Ссылки

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

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

e-olymp 74. Паук и муха — 2

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

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

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

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

Одно число – расстояние, на которое переместится паук, посчитанное с точностью до 2-х знаков после запятой.

Тесты

Входные данные Выходные данные
[latex]A[/latex] [latex]B[/latex] [latex]C[/latex] [latex]X1[/latex] [latex]Y1[/latex] [latex]X2[/latex] [latex]Y2[/latex] [latex]Z2[/latex] [latex]S[/latex]
[latex]4[/latex] [latex]7[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]8.06[/latex]
[latex]145[/latex] [latex]26[/latex] [latex]306[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]0[/latex] [latex]305[/latex] [latex]309.34[/latex]
[latex]26[/latex] [latex]18[/latex] [latex]53[/latex] [latex]24[/latex] [latex]15[/latex] [latex]24[/latex] [latex]1[/latex] [latex]53[/latex] [latex]58.52[/latex]
[latex]89[/latex] [latex]89[/latex] [latex]189[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]89[/latex] [latex]16[/latex] [latex]70.77[/latex]
[latex]18[/latex] [latex]26[/latex] [latex]145[/latex] [latex]14[/latex] [latex]2[/latex] [latex]17[/latex] [latex]26[/latex] [latex]141[/latex] [latex]147.14[/latex]

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

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

Данная задача решается с помощью «разверток» комнаты: переход от трёхмерного пространства к двумерному.
Вид комнаты:

Рассмотрим такие случаи:

  1. Паук находится на полу ([latex]Z_2 = 0[/latex]);
  2. Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex] с помощью функции [latex]distance[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

  • Паук ползет по этой стенке, затем по полу. Тогда развертка будет такой:
  • Паук ползет через ближнюю к нам стенку и по полу. Тогда развертка следующая:
  • Аналогичен предыдущему случаю, только через дальнюю от нас стенку.

По этим разверткам мы можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex]. Если же паук находится в одном из углов комнаты, то мы находим наименьшее расстояние из двух вариантов развертки.
Когда же паук сидит на потолке, не соприкасаясь ни с одной из стенок, у него есть 13 вариантов:

  • Паук спускается с потолка на паутине, затем ползет точно так же, как и в самом первом случае.
  • Паук ползет по потолку, по одной из стенок и по полу. Тогда развертка будет выглядеть следующим образом (потолок можно развернуть в 4 стороны — отсюда 4 случая):
  • Паук ползет по потолку, а затем по двум соседним стенкам и по полу. Таких случаев 8, поскольку порядок следования стенок, по которым тот ползет, также важен. Развертка одного из них:

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex].

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

e-olymp 61. Уборка снега

Задача

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

При этом известно, что:

  • Снегоход может очищать только одну проезжую полосу дороги за один проход.
  • Все дороги прямые с одной полосой движения в каждом направлении.
  • Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
  • Во время очистки снега снегоход двигается со скоростью $20$ км/час, и со скоростью $50$ км/час по уже очищенной дороге.
  • Возможность проехать все дороги всегда существует.

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

Первая строка содержит два числа $x$ и $y$ $(-30000 ≤ x, y ≤ 30000)$ — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

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

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

Тесты

Входные данные Выходные данные
$0$ $0$
$0$ $0$ $-1000$ $2000$
$0$ $0$ $1000$ $2000$
$0:27$
$0$ $1000$
$0$ $0$ $0$ $3000$
$0$ $0$ $1000$ $1000$
$0$ $0$ $3000$ $0$
$3000$ $0$ $3000$ $3000$
$3000$ $3000$ $0$ $3000$
$0$ $3000$ $1000$ $2000$
$3000$ $0$ $2000$ $1000$
$3000$ $3000$ $2000$ $2000$
$1:46$
$-500$ $0$
$-1000$ $0$ $0$ $0$
$0$ $0$ $1000$ $0$
$-1000$ $1000$ $0$ $0$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1000$ $1000$ $0$ $1000$
$0$ $1000$ $0$ $0$
$0:49$
$1000$ $500$
$-1000$ $0$ $1000$ $0$
$-1000$ $1000$ $1000$ $1000$
$-1000$ $0$ $-1000$ $1000$
$1000$ $0$ $1000$ $1000$
$-1000$ $0$ $1000$ $1000$
$1000$ $0$ $-1000$ $1000$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1:20$
$500$ $-500$
$0$ $0$ $1000$ $-1000$
$1000$ $-1000$ $2000$ $0$
$2000$ $0$ $3000$ $-1000$
$3000$ $-1000$ $4000$ $0$
$4000$ $0$ $5000$ $-1000$
$5000$ $-1000$ $6000$ $0$
$0$ $0$ $8000$ $0$
$1:39$

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

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

Начало пути всегда находится на одной из данных дорог. Составим оптимальный алгоритм движения снегохода. По каждой из дорог необходимо проехать в одну и другую сторону. Снегоход может начинать движение в любую сторону. Во время движения ему необходимо двигаться прямо, не разворачиваясь, настолько долго, насколько это возможно. В случае, если на пути следования снегоходу встречается поворот, ему необходимо повернуть и далее работать по тому же алгоритму, принимая за начальную точку точку поворота. После возвращения из поворота снегоход должен продолжить движение по алгоритму. Когда снегоход попадает в тупик, возвращается на перекресток, на котором был совершен поворот или попадает в начальную точку, ему необходимо развернуться и двигаться обратно по той же траектории. По возвращении в начальную точку снегоход должен, в случае необходимости, двигаться во все оставшиеся стороны по такому же алгоритму. Таким образом, при движении по такому алгоритму, снегоход будет проезжать по каждой дороге по одному разу в каждую сторону, то есть не будет нигде проезжать «лишние» километры, следовательно время, за которое снегоход может объехать все дороги по одному разу в каждую сторону и есть искомым. Таким образом нам необходимо посчитать сумму длин всех дорог $L$, координаты начала и конца которых даны во входном потоке. Снегоход всегда двигается со скоростью $V = 20 км/час = \frac{1000}{3}м/мин$. По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах:
$t = \frac{2L}{V} = \frac{3L}{500}$.
Округлив полученное значение $t$ до целых минут и представив это время в виде часов и минут, получаем ответ.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 13. Паук и муха

Задача

В пустой прямоугольной комнате размерами [latex]A \times B \times C[/latex] (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке — координаты мухи [latex]X_1[/latex], [latex]Y_1[/latex] и паука [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex].

Все входные данные — целые числа, не превышающие 500.

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

Единственное число — расстояние, на которое переместится паук, вычисленное с точностью до 2-х знаков после запятой.

Тесты

Входные данные Выходные данные
$3$ $4$ $8$

$0$ $0$ $3$ $4$ $0$

$5.00$
$2$ $2$ $8$

$1$ $1$ $2$ $1$ $4$

$5.00$
$6$ $4$ $3$

$5$ $1$ $0$ $2$ $1$

$6.08$
$30$ $60$ $27$

$13$ $21$ $8$ $0$ $17$

$38.33$
$40$ $40$ $40$

$10$ $5$ $8$ $40$ $37$

$72.03$

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

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

Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции [latex]distance[/latex].
В простейшем случае, если паук находится на полу комнаты, т.е. его координата [latex]Z_2[/latex] нулевая, координаты паука [latex]X_2[/latex] и [latex]Y_2[/latex] в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции [latex]distance[/latex].
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

Условие задачи на сайте E-Olymp
Код решения задачи

ML33. Угол между вектором и осями координат

Задача

Найдите углы между вектором [latex] \overrightarrow{a}=(x,y,z)[/latex] и координатными осями [latex]Ox, Oy, Oz[/latex].

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

Координаты вектора [latex]\overrightarrow{a}=(x,y,z)[/latex].

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

Угол между заданным вектором и [latex]Ox[/latex].
Угол между заданным вектором и [latex]Oy[/latex].
Угол между заданным вектором и [latex]Oz[/latex].

Тесты

Входные
данные
Выходные
данные
x y z угол c Ox угол c Oy угол c Oz
0 0 1 90 90 0
0 9999.99 0 90 0 90
1 1 1 54.7456 54.7456 54.7456
-9999.5 -9999.5 -9999.5 -54.7456 -54.7456 -54.7456
0 0 0 невозможно при нулевом векторе

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

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

Для начала проверим не является ли заданный вектор нулевым, так как он не будет образовывать угол между векторами. Если это нулевой, то выводить, что это невозможно при нулевом векторе. При другом условии решим задачу,а поскольку в условии нам даны координаты только 1 вектора, а для вычисления угла между 2 векторами нужно 2 пары координат, то будем считать, что [latex] Ox(1,0,0) [/latex], [latex] Oy(0,1,0) [/latex],[latex] Oz(0,0,1) [/latex].
Теперь мы можем вычислить угол между векторами через формулу[latex] \cos{ |\widehat { a,b } }|=\frac { \overrightarrow { a } \overrightarrow { b } }{ \left| \overrightarrow { a } \right| \left| \overrightarrow { b } \right| } [/latex], где [latex] \overrightarrow { a } \overrightarrow { b }=\ x_a\cdot{x_b}+y_a\cdot{y_b}+z_a\cdot{z_b}\[/latex] и [latex] { \left| \overrightarrow { a } \right| }=\sqrt{x_a^2+y_a^2+z_a^2} [/latex], которую можно сократить в соответствии с нашими значениями координат [latex]Ox,Oy,Oz [/latex] и в итоге получаем формулу [latex] \arccos=\frac{o}{\sqrt{x_a^2+y_a^2+z_a^2}} [/latex], где [latex] O [/latex] ось координат и [latex]o [/latex] значение по этой оси координат. В эту формулу поочередно подставляем наши значения и получаем косинусы углов между осями координат и заданным вектором. Для вычисления углов в радианах воспользуемся встроенной функцией [latex] acos [/latex], а для вычисления в градусах домножим полученный результат на 180 и разделим на встроенное значение числа [latex] \pi [/latex].

Ссылки
Ideone

Mif 8

Задача

Условие взято отсюда

Четырёхугольник [latex]ABCD[/latex] задан на плоскости целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Из характеристик указать наиболее частную.

Тесты

[latex]a_1[/latex]   [latex]a_2[/latex] [latex]b_1[/latex] [latex]b_2[/latex] [latex]c_1[/latex][latex]c_2[/latex] [latex]d_1[/latex] [latex]d_2[/latex]                                                   Ответ
0 0 1 0 1 1 0 1   квадрат
0 -3 2 0 0 3 -2 0 ромб
0 0 4 0 4 1 1 4 прямоугольник
0 0 10 0 12 4 2 4 пaраллелограмм
0 0  2 0  1 1  0 1 трапеция
0 0  0 2  1 1  1 0 трапеция
-4 -5 -15 7 5 8 6 -7 произвольный
 0 0 1 0 10 20  -5 7 произвольный

 

Код

 

Решение

Для начала стоит найти длины всех сторон:

[latex]AB^{2}=((a1-b1)^{2}+(a2-b2)^{2})[/latex]. (аналогично для остальных сторон)

Затем можно найти длины диагоналей четырёхугольника

[latex]AC^{2}=((a1-c1)^{2}+(a2-c2)^{2})[/latex]. (аналогично для [latex]BD[/latex]).

Через условие задаем равность противоположных сторон [latex]AB=CD[/latex] и  [latex]BC=DA[/latex]:

  1. У ромба смежные стороны равны, но если у ромба диагонали равны, то это квадрат;
  2. Если четырёхугольник не является квадратом, но диагонали равны, то это прямоугольник;
  3. В противном случае — параллелограмм.

Если одна из пар противополижных сторон параллельны, то данный четырёхугольник — трапеция. Впротивном случае — произвольный четырёхугольник.

Код на ideone

e-olymp 60. Площадь многоугольника

Задача. Площадь многоугольника

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

Заданы координаты [latex]n[/latex] последовательных вершин многоугольника. Определить его площадь.

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

Первая строка содержит количество вершин многоугольника [latex]n[/latex]. В следующих [latex]n[/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex]x_i, y_i[/latex]. Известно, что [latex]3 \leq n \leq 1000, -1000 \leq x[i], y[i] \leq 1000[/latex].

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

Площадь многоугольника [latex]S[/latex], вычисленная с точностью до трех десятичных знаков.

Также условие задачи можно посмотреть здесь.

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

Входные данные ([latex]n[/latex], [latex]x_i, y_i[/latex]) Выходные данные
1. 3, (0, 0), (0, 2), (2, 0) 2.000
2. 4, (-1000,  500), (-500, 1000), (2, 10),  (35, 60) 339865.000
3. 10, (51, -20), (15, 3), (45, 200), (100, -100), (201, 55), (70, -80), (25, 333), (999, 0), (500, 77), (5, -6) 124562.500
4. 5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2) 1446.000

Реализация

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

Даны координаты последовательных [latex]n[/latex] вершин многоугольника: [latex]x_i, y_i[/latex]. Для того, чтобы вычислить его площадь, воспользуемся формулой: [latex]S=\frac{1}{2}\cdot |\sum_{i=1}^{n}{(x_i + x_{i+1})\cdot (y_i — y_{i+1})}|[/latex], где [latex]x_0, y_0=x_{n+1}, y_{n+1}[/latex].

Подробнее о вычислении площади произвольного многоугольника можно прочесть здесь.

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

Ссылка на засчитанное решение на e-olymp.com.

Mif 17.15

Задача Mif17.15

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

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

Viktoriya_Kudymovskaya (1)

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

В одной строке задано два числа – координаты точки latex[/latex].

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

Вывести: «Принадлежит» или «Не принадлежит»(без кавычек).

Также условие задачи можно посмотреть здесь.

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

Входные данные Выходные данные
1. 1.5 7 Не принадлежит
2. 3 4 Не принадлежит
3. 2 -3.6 Принадлежит
4. 5 0 Принадлежит
5. 0 1 Не принадлежит
6. 0 -4 Не принадлежит
7. 3 3 Принадлежит
8. 2 3 Принадлежит

Реализация

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

Пусть на плоскости дан треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]C(x_3, y_3)[/latex]. А  [latex]D(x, y)[/latex] — произвольная точка на координатной плоскости. Положим, [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] — векторы.

  1. Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
  2. Если векторы заданы своими координатами [latex]a(x_1, y_1), b(x_2, y_2)[/latex], то их косое произведение [latex][a,b]=x_1\cdot y_2 — x_2\cdot y_1[/latex]. Пользуясь данной формулой, запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]D(x, y)[/latex]: [latex]k=x_1y_2 — x_2y_1 — x_1y + xy_1 + x_2y — xy_2=(x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex].
  3. Далее запишем косое произведение векторов [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex]: [latex]m=x_2y_3 — x_3y_2 — x_2y + xy_2 + x_3y — xy_3=(x_2 -x)\cdot (y_ 3- y_2) — (x_3 — x_2)\cdot (y_2 — y)[/latex].
  4. Запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] : [latex]n=x_1y_3 — x_3y_1 — x_1y + xy_1 + x_3y — xy_3=(x_3 — x)\cdot (y_1 — y_3) — (x_1 — x_3)\cdot (y_3 — y)[/latex].
  5. Если [latex]k \leq 0 [/latex] и [latex]m \leq 0[/latex] и [latex]n \leq 0[/latex]  или [latex]k \geq 0[/latex] и [latex]m \geq 0[/latex] и [latex]n \geq 0[/latex], то делаем вывод: точка принадлежит треугольнику.
  6. Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

Ознакомиться с теоретическим материалом можно здесь.

Для запроса на выполнение следует перейти по ссылке.

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

Gresh
Условие:

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

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

Два числа — координаты точки.

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

Слово «Yes», если точка принадлежит фигуре, в противном случае -«No».

Тесты:

[latex]x[/latex] [latex]y[/latex] Result
6 0 Yes
0 0 Yes
5 2 No
-6 1 No

 

Описание решения:

Точка будет принадлежит фигуре тогда и только тогда, когда будут выполняться группы условий: или оба числа не отрицательные и их сумма не превышает 6, или оба числа не положительные, и их сумма не меньше 6. если одно из этих условий выполняется, то выводим «Yes», а иначе — «No».

Здесь решенная задача на сайте 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 находится здесь.

 

 

Ю2.6

Условие

Четырёхугольник [latex]ABCD[/latex] задан координатами своих вершин на плоскости: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex] и [latex]C(x_c,y_c)[/latex], [latex]D(x_d,y_d)[/latex]. Определить тип четырёхугольника: прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Учесть погрешность вычислений.

Замечание:  Для устранения дополнительных источников погрешности рекомендуется использовать аппарат векторной алгебры: коллинеарность, равенство и ортогональность векторов — сторон четырёхугольника.

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

В одной строке заданы 8 чисел [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] — координаты вершин четырёхугольника [latex]ABCD[/latex],  значения которых не превышают по модулю [latex]50[/latex].

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

  1. В первой строке вывести: «Тип четырёхугольника: «(без кавычек).
  2. Во второй строке вывести:  «Произвольный четырёхугольник» или «Прямоугольник» или «Параллелограмм» или «Трапеция»(без кавычек). Одно исключает другое.

Также условие задачи можно посмотреть, скачав ознакомительную версию задачника А.Юркина здесь.

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

Координаты [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] Вердикт (тип четырёхугольника)
1. -5 -4 -1 -2 -4 3 -1 -8 Параллелограмм
2.  -2 -3 7 3 -2 1 7 1  Трапеция
 3. 0 0 1 1 0 1 1 0  Прямоугольник
 4.  50 -20 3 -50 7 6 2 3  Произвольный четырёхугольник
5. 2 -3 -6 -1 4 7 6 3 Параллелограмм
6. 1 -5 6 20 2 0 13 -9 Произвольный четырёхугольник
7. 0 1 2 1 0 1 1 0 Параллелограмм
8. -6 0 6 0 1 5 -4 -8 Прямоугольник

Реализация

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

  1. Задан четырёхугольник [latex]ABCD[/latex] с такими координатами вершин: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex], [latex]C(x_c,y_c)[/latex] и [latex]D(x_d,y_d)[/latex]. В данной задаче будет уместным использование аппарата векторной алгебры.  Пусть стороны четырёхугольника — векторы.
  2. Очевидно, что для того, чтобы определить тип данного четырёхугольника, необходимо воспользоваться известными свойствами, а именно: свойствами прямоугольника, параллелограмма и трапеции. Так как в задаче используется аппарат векторной алгебры, обращаемся к таким свойствам векторов, как коллинеарность и равенство.
  3. Сразу же установим: является ли четырёхугольник трапецией. Проверим одну из двух пар сторон на параллельность. Для этого воспользуемся условием коллинеарности векторов на плоскости: [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}[/latex], если [latex]a_i, b_i\ne0[/latex].  Координаты векторов [latex]\vec{b}[/latex] и [latex]\vec{d}[/latex] должны быть пропорциональны, что означает, что соответствующие стороны параллельны. Следовательно, [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Или же координаты векторов [latex]\vec{a}[/latex] и [latex]\vec{c}[/latex] должны быть пропорциональны. Проверяем: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex]. Если условие не выполняется, четырёхугольник произвольный. Если, напротив, координаты хотя бы одной пары векторов пропорциональны, четырёхугольник является трапецией.
  4. Если четырёхугольник — параллелограмм, то обе пары его противоположных сторон параллельны. Проверим, выполняется ли: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex] и [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Если условие выполняется, то заданный четырёхугольник — параллелограмм.
  5. Частным случаем параллелограмма является прямоугольник. Диагонали [latex] AC, BD[/latex] обозначим как [latex] l, m[/latex] соответственно. Пусть [latex] l, m[/latex] — векторы.  Вычислим длины векторов [latex]\vec{l}[/latex], [latex]\vec{m}[/latex], пользуясь формулой.  Получаем: [latex]\vec{|l|}= \sqrt{(x_c — x_a)\cdot (x_c -x_a) + (y_c — y_a)\cdot (y_c -y_a)}[/latex], [latex]\vec{|m|}= \sqrt{(x_d — x_b)\cdot (x_d -x_b) + (y_d — y_b)\cdot (y_d -y_b)}[/latex]. При условии, что [latex]\vec{l}=\vec{m}[/latex], имеем прямоугольник.

Более детально со свойствами и видами четырёхугольников можно ознакомиться здесь, а с основными сведениями из векторной алгебры — здесь.

Для запроса на выполнение следует перейти по ссылке.

 

 

ML18

Задача ML18

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

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

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

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex],  значения которых не превышают по модулю [latex]100[/latex].

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

Вывести периметр [latex]p[/latex] данного треугольника.

Также условие задачи можно посмотреть здесь.

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

Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex]) Выходные данные
1 2 2 5 1  0 -1 3 5 10 16.0261556346
2 1 4 5 3 6 0 10.5 -2 -1 31.9047289894
3 15 26 13 32 18 56 80 0 -6.2 212.0962807371
4 -13 68 44 99 -100 70 0 2 1 450.5748518262
5 100 9 17 18 29 88 65 -16 0.36 310.4318979186

Реализация

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

  1. Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
  2. Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
  3. Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

Подробнее о декартовой системе координат можно прочесть здесь.

Для запроса на выполнение следует перейти по ссылке.