e-olymp 5071. Проверка на неориенитрованность

Задача. Проверка на неориенитрованность

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

По заданной квадратной матрице [latex]n\times n[/latex]  из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

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

Входной файл содержит число [latex]n(1\leq n\leq 100)[/latex] — размер матрицы, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — саму матрицу.

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

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

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

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

Входные данные Выходные данные
1. 3
0 1 1
1 0 1
1 1 0
YES
2. 3
0 1 0
1 0 1
1 1 0
NO
3. 3
0 1 0
1 1 1
0 1 0
NO

Реализация

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

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j]=a[j][i][/latex]. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

Подробнее о графах и матрице смежности можно прочесть, используя следующие интернет-ресурсы:

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

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

A305

Задача A305

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

Даны действительные числа [latex]a_{1},\dots,a_{n}[/latex]. Оставить без изменения последовательность [latex]a_{1},\dots,a_{n}[/latex], если она упорядочена по неубыванию или по невозрастанию; в противном случае удалить из последовательности те члены, порядковые номера которых кратны четырём, сохранив прежним порядок оставленных членов.

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

Входные данные Выходные данные
1. 5
-1 2 3 4 5
-1 2 3 4 5
2. 6
6 0 2 3 4 6.7
0 2 3 6.7
3. 10
1 2 5 7 -10 3 1 3 2 1
2 5 7 3 1 3 1
4. 5
1 5 6 7.5 0
5 6 7.5
5. 3
-23 46 -80
46 -80

Реализация

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

Считываем все действительные числа до конца входного потока и записываем их в вектор v1. Проверяем, упорядочена ли последовательность по возрастанию или по убыванию. Если да, выводим на экран исходную последовательность без изменений с помощью функции copy() и итератора вывода ostream_iterator, который записывает элементы последовательно в выходной поток. Если же последовательность не упорядочена ни по убыванию, ни по возрастанию, удаляем из неё элементы, порядковые номера которых кратны четырём. Важно сохранить прежним порядок оставленных членов.
Работаем следующим образом:
1. Создаём вектор v_2.
2. Уменьшаем размер контейнера с помощью функции resize(): v2.resize(size_of_the_sequence - temp). Инициализируем переменную  size_of_the_sequence значением ноль.
3. Если порядковый номер элемента неупорядоченной последовательности кратен четырём, то увеличиваем количество элементов на единицу с каждой итерацией. Иначе, присваиваем вектору v_2 значение вектора v_1: v2[i - size_of_the_sequence] = v1[i].
4. Уменьшаем размер контейнера v_1. Присваиваем вектору v_1 значение вектора v_2.
5. С помощью функции shrink_to_fit() уменьшаем количество используемой памяти вектора v_1.
6. Извлекаем все элементы из вектора v_2 с помощью функции clear().

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

e-olymp 6128. Простой дек

Задача. Простой дек

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

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front,
  • pop_back,
  • front,
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

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

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

Входные данные Выходные данные
1. push_back 3
push_front 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit
ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye
2. push_front 5
pop_front
size
push_back 3
push_front 10
back
pop_back
size
clear
front
exit
ok
5
0
ok
ok
3
3
1
ok
-1
bye
3. push_front 1
push_back 12
back
front
size
pop_front
size
exit
ok
ok
12
1
2
1
1
bye

Реализация

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

Реализуем двустороннюю очередь с помощью массива. Ввиду особенности структуры дека, необходимым является указание области, активной во время выполнения операций push_front, push_back, pop_front, pop_back, front и back. Это либо начало дека(переменная start), либо его конец(переменная end).
1. Перед выполнением операций push_front и push_back обязательной является проверка дека на заполненность и соответственно на пустоту. Таким образом, если размер дека равен максимально допустимому количеству элементов в структуре данных, программа выводит Full — ни одна из двух вышеупомянутых команд не выполняется. Аналогично, если размер дека равен нулю, увеличиваем его на единицу. Иначе: команды успешно выполняются с проверкой условий, представленных в коде программы. Программа выводит «ok».
2. Далее переходим к командам pop_front и pop_back. Здесь, как и в случае предыдущих операций, в первую очередь проверяем дек на пустоту. Если двусторонняя очередь не содержит элементов, то программа выводит -1. Важной также является проверка на равенство начала и конца дека, в этом случае нужно уменьшить размер структуры на единицу. Если дек содержит хотя бы один элемент, команды успешно выполняются и выводятся значения извлекаемых элементов.
3. Аналогично, перед выполнением команд front и back проверяем, содержит ли дек хотя бы один элемент. Если нет, выводится -1. Иначе: выводятся значения первого и последнего элемента соответственно.
4. Используем команду size, чтобы получить размер дека. Программа выводит количество элементов в деке.
5. Далее, с помощью команды clear удаляем из дека все элементы: присваиваем переменной _size(размер дека) и переменным start и end значение ноль. Программа выводит «ok».
6. Команда exit выводит «bye» — программа завершает работу.
Реализация вывода на экран всех требуемых значений происходит в теле функции main() с помощью строки s.

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

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

A278

Задача A278

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

Даны натуральные числа [latex]n_{1},\dots,n_{m}[/latex], действительные числа [latex]x_{1},\dots,x_{m}[/latex]. Вычислить [latex]\frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}[/latex].

 

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

Входные данные Выходные данные
1. 1 2 4 -1 -0.4
2. 1 2 3 4 5 0.6 1.88889
3. 5 -2 1 0.2 3 -3 2 0 -1.70909
4. 10 3.3 4 0.4 6 0.01 8 1 1 8 1.7469
5. 3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1 4.58095

Реализация (класс vector)

Алгоритм решения (класс vector)

Считываем все натуральные числа до конца входного потока и записываем их в вектор [latex]n[/latex]. Аналогично, считываем все действительные числа до конца входного потока и записываем их в вектор [latex]x[/latex].

  1. Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму sum1.
  2. Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму  sum2.
  3. Находим результат res от деления sum1 на  sum2.

Реализация (потоковая обработка)

Алгоритм решения (потоковая обработка)

Считываем все натуральные числа до конца входного потока и записываем их в переменную member1. Аналогично, считываем все действительные числа до конца входного потока и записываем их в переменную  member2.
Пока вводятся данные:

  1. Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму sum1.
  2. Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму  sum2.
  3. Находим результат res от деления sum1 на  sum2.

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

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

e-olymp 2162. Палиндром

Задача. Палиндром

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

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

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

Дана строка [latex]S[/latex], [latex]|S| \leq 255[/latex], состоящая из строчных латинских букв и пробелов. Под [latex]|S|[/latex] подразумевается длина строки.

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

Требуется вывести «YES«, если текст является палиндромом, «NO» если не является.

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

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

Входные данные Выходные данные
1. palindrom NO
2. a roza upala na lapu azora YES
3. my gym YES
4. character NO

Реализация (с использованием c-string)

Алгоритм решения (c-string)

С помощью функции [latex]strcmp()[/latex] сравниваем символы строк [latex] s_1[/latex] и [latex]s_2[/latex], предварительно учтя тот факт, что пробел при чтении никак не произносится. Если они идентичны,  введенный текст одинаково читается слева направо и справа налево, то есть является палиндромом. В противном случае, текст палиндромом не является. Важно отметить, что функция [latex]strcmp()[/latex] учитывает регистр введенных символов, согласно условию мы должны использовать строчные латинские буквы.

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

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

Реализация (с использованием string)

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

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

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

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

MLoop 20

Задача. Вычислите с точностью [latex]\varepsilon[/latex] сумму ряда [latex]\sum_{i=1}^{\infty}{\frac{i}{3^i}}[/latex].

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

Точность [latex]\varepsilon[/latex].

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

Вывести значение суммы ряда.

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

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

Входные данные Выходные данные
1. 0.1 0.666667
2. 0.01 0.736626
3. 0.001 0.749276
4. 0.0001 0.749903
5. 0.0000001 0.75

Реализация (первый вариант кода)

Реализация (второй вариант кода)

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

  1. Выводим формулу для вычисления значения каждого последующего члена ряда: [latex]a_{n+1}=a_n\cdot \frac{i+1}{3^{i+1}}\cdot \frac{3^i}{i}=a_n\cdot \frac{i+1}{3i}[/latex].
  2. Вычисляем значение первого члена ряда: [latex]a[/latex]: [latex]a=\frac{i}{3^i}=\frac{1}{3}[/latex].
  3. Присваиваем [latex]sum[/latex] значение первого члена ряда.
  4. Абсолютное значение каждого последующего члена ряда сравниваем с [latex]\varepsilon[/latex]: при условии, что [latex]|a_{n+1}|\geq\varepsilon[/latex], накапливается сумма (значение суммы увеличивается на очередной член ряда [latex]a_{n+1}[/latex]). Если же [latex]|a_{n+1}|<\varepsilon[/latex], выводится значение суммы ряда.

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

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

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

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

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

Ю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].

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

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

 

e-olymp 63. Анфиса и цветы

Задача. Анфиса и цветы

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

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

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

<

h4″>Входные данные

В одной строке заданы два числа m и n [latex]\left( n, 0 < m, n ≤ 2\cdot 10^9 \right)[/latex].

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

Вывести наибольшее количество кусочков сыра, которые может получить Анфиса.

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

Реализация

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

Входные данные (m, n) Выходные данные
1 2, 3 3
2 3, 3 5
3 3, 4 7
4 4, 3 7
6 5, 7 25

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

Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему,  съедает latex\cdot(n-1)[/latex]  цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.

Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot(n-1)+1[/latex], где p — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].

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

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