e-olymp 145. Квадраты

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

Задача

Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять только из одного отрезка.

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

В первой строке находится количество отрезков $n \left(1 \leqslant n\leqslant 10^6\right)$. Во второй строке заданы $n$ натуральных чисел — длины отрезков, числовые значения которых не превышают $100$.

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

Вывести максимально возможное количество квадратов, которое можно составить из заданных отрезков.

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 9
2 2 4 2 3 2 1 2 4
1
2 11
2 2 4 2 2 4 2 2 1 2 2
2
3 5
8 9 8 9 11
0

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

Решение

Пусть имеется $k$ отрезков одинаковой длины. Тогда из них можно составить $\frac{k}{4}$ квадрата. Длины отрезков изменяются от $1$  до $100$. Подсчитываем количество отрезков длины $i\left(1\leqslant i\leqslant 100\right)$ в массив $a\left[i\right]$. Тогда максимально возможное количество квадратов, которое можно составить из данных отрезков, равно $$\frac{a\left[1\right]+a\left[2\right]+\dots +a\left[100\right]}{4}.$$
Для этого совершим сортировку подсчетом. В ячейке a[i] подсчитываем количество отрезков длины i . В переменную res  подсчитываем количество квадратов, которое можно построить.

Ссылки

Условие задачи на e-olymp

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

Сортировка подсчетом на Wikipedia

e-olymp 944. Площадь пирамиды

Задача

Треугольная пирамида задана координатами своих вершин [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] S(x_4; y_4; z_4). [/latex] Определить площадь полной поверхности пирамиды.

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

В четырех строках заданы координаты [latex] x, y, z [/latex] вершин пирамиды. Все числа целые, не превышающие по модулю 100.

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

Вывести полную поверхность пирамиды с точностью до десятых.

Тесты

Входные данные Выходные данные
1 -3 0 0 69,8
0 6 0
3 0 0
0 2 5
2 2 4 8 159,1
2 -6 9
5 -4 0
1 3 0
3 5 0 1 107,3
4 1 7
-9 0 4
6 2 8

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

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

Для того, чтобы найти площадь полной поверхности пирамиды, необходимо найти площади треугольников, которые являются гранями пирамиды.
Для нахождения площади треугольника можно воспользоваться формулой Герона: [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)} [/latex],где [latex] p [/latex]-полупериметр треугольника, [latex] a,b,c [/latex] — стороны треугольника. Чтобы воспользоваться формулой Герона, необходимо предварительно найти длины сторон треугольников, используя формулу нахождения длин отрезков по координатам концов отрезка: [latex] |AB|=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2+(z_b-z_a)^2} [/latex], где [latex] А,В [/latex] — концы отрезка, [latex] x_a, y_a,z_a [/latex] — координаты [latex] А [/latex], [latex] x_b, y_b,z_b [/latex] — координаты [latex] В [/latex].
Найденные площади всех треугольников, из которых состоит пирамида, складываем и получаем искомую площадь полной поверхности пирамиды.

Ссылки

e-olymp
ideone