Optical Optimization
The state of a linearly polarized laser beam is represented by a pair of equal and opposite 2D vectors (blue), parametrized by (E, θ), where E ≥ 0 is the beam's field strength and θ, 0° ≤ θ < 180° is the beam's polarization angle. This representation is illustrated on the right:
A polarization filter is represented by a line (red) through the origin, parametrized by its filter angle φ, 0° ≤ φ < 180°. When a filter φ is applied to a beam (E_a, θ_a), a new beam (E_b, θ_b) emerges, and is evaluated by
E_b = E_b|cos(θ_a−φ)|, θ_b = φ,
i.e. the new beam loses strength, and takes on the angle of the filter. Geometrically, the opposing vectors represented by (E_a,θ_a) are "orthogonally projected" onto the line represented by φ, forming new opposing vectors represented by (E_b,θ_b), as shown on the left:
Let us begin with a beam (E_0, θ_0) = (1, 0°). If we apply a filter φ_y = 90°, then we would obtain a beam with (E_y, θ_y) = (cos(90°), 90°) = (0, 90°), i.e. a beam with strength zero.
Suppose we have another filter ξ_x = 45°, and we apply it to (E_0,θ_0) before applying φ_y = 90°. We would obtain (E_x,θ_x) = (cos(45°),45°) first, followed by (E_y,θ_y) = (cos^2(45°),90°) = (0.5,90°). Therefore adding an extra filter can increase the strength of the final beam! This is illustrated by a double-projection:
In this problem, we would like to pass a beam (E_0, θ_0) = (1, 0°) sequentially through m fixed filters φ_1, φ_2, ..., φ_m. The intermediate beam emerging from filter φ_i is (E_i, θ_i) = (E_i, φ_i). We also have n extra filters that can have any angle, and can be placed before any fixed filter. Our objective is to find the maximum possible output field strength E_m.
Suppose each fixed filter φ_i is allotted k_i extra filters that interact with beam (E_i_{−1}, θ_i_{−1}) first (n = k_1 + k_2 + ... + k_m). The k_i extra filters before φ_i will have angles that evenly span between θ_i_{−1} and θ_i = φ_i, along the acute (or right) angle between θ_i_{−1} and φ_i. An example with k_i = 3 is shown on the right:
Using this method, the following formula can be derived:
where f(Δ,k) for 0° ≤ Δ < 180° and k ≥ 0 is defined as:
.
If k_i = 0 (no extra filter inserted) the formula degenerates into E_i = E_{i−1}|cos(θ_i−φ_i_{−1})|.
Since (E_0, θ_0) = (1, 0°), the expression for the final output strength is:
.
Given m, n, and φ_1, φ_2, ..., φ_m, your task is to compute the maximum possible E_m.
Input
The first input line contains the number of test cases N, 1 ≤ N ≤ 100.
Each test case begins with integers m and n, separated by space. m lines follow, each containing an integer φ_i (for 1 ≤ i ≤ n).
m is the number of fixed filters, and satisfies 1 ≤ m ≤ 10.
n is the number of extra filters, and satisfies 0 ≤ n ≤ 100.
φ_i is the filter angle (in degrees) for the i'th fixed filter, and satisfies 0 ≤ m < 180.
Note: Remember to convert degrees to radians before using cos().
Output
For each test case, print the maximum possible magnitude for φ_m, to 8 decimal places.