Оптична оптимізація
Стан лінійно поляризованого лазерного променя описується парою рівних і протилежних 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 знаків після коми.