Лена и зеркало

Л ена любит смотреть в зеркало. Она любит не только смотреть на своё отражение, но и изучать законы оптики, наблюдая за ходом световых лучей.

Так как Солнце находится на достаточно большом расстоянии от Земли, при расчётах часто считают Солнце бесконечно удалённой точкой. В этом случае световые лучи, испускаемые Солнцем, считают параллельными друг другу.

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

Пусть зеркало наклонено так, что в некоторой системе координат его можно задать как прямую, имеющую уравнение y = kx + b. Направление падения солнечных лучей задаётся единичным вектором a.

Требуется найти направление отражения лучей, а именно, требуется найти единичный вектор c.

Примечание. По законам оптики, свет отражается так, что угол падения равен углу отражения (α = β на рисунке).

Формат входного файла

Входной файл содержит три вещественных числа k x₁ y₁ — угловой коэффициент прямой и координаты вектора a.

Длина вектора a приближённо равна 1.

Формат выходного файла

Выходной файл должен содержать два вещественных числа x₂ y₂ — координаты вектора c.

Длина вектора c должна быть приближённо равна 1.

Координаты вектора c должны быть выведены с точностью до 3-х знаков после запятой.

Ограничения

−1000 ≤ k ≤ 1000

Примеры тестов

№	Входной файл	Выходной файл
1	0 0.7071067812 -0.7071067812	0.7071067812 0.7071067812
2	1 1 0	0 1

Разбор

Пусть l — единичный направляющий вектор прямой, n — единичный вектор нормали к прямой. Эти векторы перпендикулярны друг другу.

Рассмотрим базис, состоящий из векторов l и n. Разложим вектор a по этому базису: a = Nn + Ll.

Тогда вектор c можно найти по формуле: c = −Nn + Ll = 2 Ll − a.

Так как базис {n, l} ортогональный (т.е. векторы базиса перпендикулярны друг другу) и векторы базиса единичные, координату L можно найти по формуле: L = a · l.

Следовательно, c = 2(a · l)l − a.

Найдём направляющий вектор. Выберем на прямой две точки: A(0, b) и B(1, k + b). Тогда в качестве направляющего вектора можно взять вектор AB{1, k}. Единичный направляющий вектор: .

program mirror;

var

k, x1, y1: extended;

len: extended;

xl, yl: extended;

sc: extended;

x2, y2: extended;

begin

assign(input, 'input.txt');

reset(input);

assign(output, 'output.txt');

rewrite(output);

read(k, x1, y1);

len := sqrt(sqr(x1) + sqr(y1));

xl := 1/sqrt(sqr(k)+1);

yl := k/sqrt(sqr(k)+1);

sc := x1*xl + y1*yl;

x2 := 2*sc*xl - x1;

y2 := 2*sc*yl - y1;

write(x2:0:5, ' ', y2:0:5);

close(input);

close(output);

end.

Макет города Условие

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

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

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

Формат входного файла

Входной файл содержит целое число N — количество зданий.

Далее следуют N пятёрок целых чисел: x_i y_i u_i v_i h_i, где (x_i, y_i) и (u_i, v_i) — координаты двух противоположных углов основания здания в сантиметрах, h_i — высота здания в сантиметрах.

Основания зданий представляют собой прямоугольники со сторонами, параллельными осям координат.

Формат выходного файла

Выходной файл должен содержать целое число S — искомую площадь в квадратных сантиметрах.

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ x_i < u_i ≤ 10000

0 ≤ y_i < v_i ≤ 10000

0 < h_i ≤ 100

Сумма площадей верхних и боковых граней всех зданий без учёта соприкасающихся частей не превосходит 10⁹.

Примеры тестов

№	Входной файл	Выходной файл
1	1 0 5 5 7 3	52
2	2 0 5 5 7 3 3 2 6 5 4	97

Разбор

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

,

г де S_i — площадь поверхности i-го здания (сумма площадей верхней грани и боковых граней), S_ij — площадь соприкосновения i-го и j-го зданий.

S_i можно вычислить по формуле:

.

S_ij можно вычислить по формуле:

,

г де l_ij — длина пересечения оснований i-го и j-го зданий:

,

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

Если, например, v_i = y_j (см. рис.), то прямоугольники могут пересекаться по горизонтальному отрезку, тогда , равняется длине пересечения отрезков [x_i, u_i] и [x_j, u_j].

Таким образом, для вычисления искомой площади цветной бумаги необходимо перебрать все пары прямоугольников, для которых v_i = y_j или u_i = x_j, и вычислить для этих прямоугольников l_ij.