Оптическая оптимизация
Состояние линейно поляризованного лазерного луча описывается парой равных и противоположных 2D векторов (синие), параметризованных значениями (E, θ), где E ≥ 0 — это сила поля луча, а θ, 0° ≤ θ < 180° — это угол поляризации луча. Это представление иллюстрируется справа:
Поляризационный фильтр представлен линией (красной), проходящей через начало координат, параметризованной своим углом фильтра φ, 0° ≤ φ < 180°. Когда фильтр φ применяется к лучу (E_a, θ_a), появляется новый луч (E_b, θ_b), который определяется по формуле
E_b = E_a|cos(θ_a−φ)|, θ_b = φ,
то есть новый луч теряет силу и принимает угол фильтра. Геометрически противоположные векторы, представленные (E_a,θ_a), "ортогонально проецируются" на линию, представленную φ, образуя новые противоположные векторы, представленные (E_b,θ_b), как показано слева:
Начнем с луча (E_0, θ_0) = (1, 0°). Если мы применим фильтр φ_y = 90°, то получим луч с (E_y, θ_y) = (cos(90°), 90°) = (0, 90°), то есть луч с нулевой силой.
Предположим, у нас есть еще один фильтр ξ_x = 45°, и мы применяем его к (E_0,θ_0) перед применением φ_y = 90°. Сначала мы получим (E_x,θ_x) = (cos(45°),45°), а затем (E_y,θ_y) = (cos^2(45°),90°) = (0.5,90°). Таким образом, добавление дополнительного фильтра может увеличить силу конечного луча! Это иллюстрируется двойной проекцией:
В этой задаче мы хотим пропустить луч (E_0, θ_0) = (1, 0°) последовательно через m фиксированных фильтров φ_1, φ_2, ..., φ_m. Промежуточный луч, выходящий из фильтра φ_i, это (E_i, θ_i) = (E_i, φ_i). У нас также есть n дополнительных фильтров, которые могут иметь любой угол и могут быть размещены перед любым фиксированным фильтром. Наша цель — найти максимальную возможную выходную силу поля E_m.
Предположим, что каждому фиксированному фильтру φ_i выделено k_i дополнительных фильтров, которые сначала взаимодействуют с лучом (E_i_{−1}, θ_i_{−1}) (n = k_1 + k_2 + ... + k_m). k_i дополнительных фильтров перед φ_i будут иметь углы, равномерно распределенные между θ_i_{−1} и θ_i = φ_i, вдоль острого (или прямого) угла между θ_i_{−1} и φ_i. Пример с k_i = 3 показан справа:
Используя этот метод, можно вывести следующую формулу:
где f(Δ,k) для 0° ≤ Δ < 180° и k ≥ 0 определяется как:
.
Если k_i = 0 (дополнительный фильтр не вставлен), формула вырождается в E_i = E_{i−1}|cos(θ_i−φ_i_{−1})|.
Так как (E_0, θ_0) = (1, 0°), выражение для конечной выходной силы:
.
Даны m, n и φ_1, φ_2, ..., φ_m, ваша задача — вычислить максимальную возможную E_m.
Входные данные
Первая строка ввода содержит количество тестов N, 1 ≤ N ≤ 100.
Каждый тест начинается с целых чисел m и n, разделенных пробелом. Следующие m строк содержат по одному целому числу φ_i (для 1 ≤ i ≤ n).
m — количество фиксированных фильтров, и удовлетворяет 1 ≤ m ≤ 10.
n — количество дополнительных фильтров, и удовлетворяет 0 ≤ n ≤ 100.
φ_i — угол фильтра (в градусах) для i-го фиксированного фильтра, и удовлетворяет 0 ≤ m < 180.
Примечание: Не забудьте преобразовать градусы в радианы перед использованием cos().
Выходные данные
Для каждого теста выведите максимальную возможную величину для φ_m, с точностью до 8 десятичных знаков.