15470번 - Fences 스페셜 저지다국어

Your friend, Donald, has a villa surrounded by two tiers of fences, and he wants to calculate the area of land between them. He can measure the length of any fence, but Donald has no idea on calculating the area. Watson, one of Donald’s friends, notices that the fences are probably built by a computer scientist mastering the knowledge of computational geometry, because the following facts are no coincidence.

• The shape of the land inside the outer tier is a perfect circle C. Let B denote the set of points on the boundary of C.
• The shape of the land inside the inner tier is a non-self-intersecting polygon P of n vertices. I.e., two edges do not intersect if they don’t share a common vertex. Let V denote the set of vertices of P.
• All vertices of P have identical minimum distances to C. In other words, for distinct vertices (x_u, y_u),(x_v, y_v) ∈ V , we have

\[\min_{(x,y) \in B}{\sqrt{\left(x-x_u\right)^2 + \left(y-y_u\right)^2}} = \min_{(x,y) \in B}{\sqrt{\left(x-x_v\right)^2 + \left(y-y_v\right)^2}}\]

Suddenly, you know how to calculate the area of land between the two tiers of fences from the total length c of outer tier and the lengths ℓ₁, . . . , ℓ_n of the n edges of P. Note that Donald can measure these length. Could you help him to calculate the area?

The first line of the input contains a positive integer T indicating the number of test cases. Each test case consists of two lines. The first line contains two numbers c and n separated by a space. c is the total length of the outer tier, i.e., c is the perimeter of C. n is the number of vertices of P. The second line contains n positive integers ℓ1, . . . , ℓ_n indicating the lengths of edges of P.

You may assume:

• 1 ≤ T ≤ 100
• 3 ≤ n ≤ 10
• 10 ≤ c ≤ 1000
• ℓ₁, . . . , ℓ_n > 0
• P must be inside the circle C.

For each case, output the area between the two tiers of fences. Your answer will be accepted if the absolute error or the relative error is less than 10⁻⁶.