8525: 2D Internet Angel
内存限制：256 MB
时间限制：1 S
题面：传统
评测方式：Special Judge
上传者：
提交：2
通过：0
题目描述
Welcome To My Religion.
Internet Angel descends! She is aimed at saving us, humans. The people waiting to be redeemed are enclosed in what can be seen as a convex polygon of nnn vertices on a 2D plane. This convex polygon is somehow special: there exists a circle with its center at (0,0)(0,0)(0,0) that is tangent to every side of the polygon. We denote the circle by Circle A\texttt{Circle A}Circle A.
Angle Chan does not descend directly into the crowd but additionally draws a large circle with the center at (0,0)(0,0)(0,0) that can surround the whole crowd. We denote the circle by Circle B\texttt{Circle B}Circle B. Next, she will choose a location between the circle and the crowd uniformly randomly, and then for all the tangent points of each side of the polygon, she will choose a point nearest to her and follow the shortest path to the crowd.
For convenience, when inputting this convex polygon we input Circle A\texttt{Circle A}Circle A and nnn angles indicating the position of the tangent point of each side of the polygon on Circle A\texttt{Circle A}Circle A. You can check the input format and the sample to get a better understanding.
Now, Angle Chan wants to know what is the expectation of the squared distance of this shortest path.
Angle Chan does not descend directly into the crowd but additionally draws a large circle with the center at (0,0)(0,0)(0,0) that can surround the whole crowd. We denote the circle by Circle B\texttt{Circle B}Circle B. Next, she will choose a location between the circle and the crowd uniformly randomly, and then for all the tangent points of each side of the polygon, she will choose a point nearest to her and follow the shortest path to the crowd.
For convenience, when inputting this convex polygon we input Circle A\texttt{Circle A}Circle A and nnn angles indicating the position of the tangent point of each side of the polygon on Circle A\texttt{Circle A}Circle A. You can check the input format and the sample to get a better understanding.
Now, Angle Chan wants to know what is the expectation of the squared distance of this shortest path.
输入格式
The first line contains an integer T(1≤T≤20)T(1\le T \le 20)T(1≤T≤20), denoting that there are TTT test cases.
For each test case, the first line contains three integers n,R1,R2n, R_1, R_2n,R1,R2 (3≤n≤1043\le n \le 10^43≤n≤104, 1≤R1<R2≤1041\le R_1 < R_2 \le 10^41≤R1<R2≤104), indicating the number of points of the convex polygon, the radius of Circle A\texttt{Circle A}Circle A and Circle B\texttt{Circle B}Circle B respectively.
The next line contains nnn integers a1,a2,…,ana_1,a_2,\ldots, a_na1,a2,…,an (−104≤a1<a2<…<an<104-10^4 \le a_1 < a_2<\ldots<a_n < 10^4−104≤a1<a2<…<an<104), indicating that the tangent point of the iii-th side lies at (R1cosai⋅π10000,R1sinai⋅π10000)(R_1 \cos\frac{a_i\cdot \pi}{10000}, R_1 \sin\frac{a_i\cdot \pi}{10000})(R1cos(ai⋅π/10000),R1sin(ai⋅π/10000)).
It is guaranteed that all the tangent lines can form a convex polygon, and all points inside or on the sides of the convex polygon are strictly inside Circle B\texttt{Circle B}Circle B.
For each test case, the first line contains three integers n,R1,R2n, R_1, R_2n,R1,R2 (3≤n≤1043\le n \le 10^43≤n≤104, 1≤R1<R2≤1041\le R_1 < R_2 \le 10^41≤R1<R2≤104), indicating the number of points of the convex polygon, the radius of Circle A\texttt{Circle A}Circle A and Circle B\texttt{Circle B}Circle B respectively.
The next line contains nnn integers a1,a2,…,ana_1,a_2,\ldots, a_na1,a2,…,an (−104≤a1<a2<…<an<104-10^4 \le a_1 < a_2<\ldots<a_n < 10^4−104≤a1<a2<…<an<104), indicating that the tangent point of the iii-th side lies at (R1cosai⋅π10000,R1sinai⋅π10000)(R_1 \cos\frac{a_i\cdot \pi}{10000}, R_1 \sin\frac{a_i\cdot \pi}{10000})(R1cos(ai⋅π/10000),R1sin(ai⋅π/10000)).
It is guaranteed that all the tangent lines can form a convex polygon, and all points inside or on the sides of the convex polygon are strictly inside Circle B\texttt{Circle B}Circle B.
输出格式
For each test case, print the expected squared distance in a line. Your answer will be considered correct if the absolute or relative error between yours and the standard answer is no more than 10−610^{-6}10−6.
输入样例 复制
1
4 2 4
-10000 -5000 0 5000输出样例 复制
2.893122167156数据范围与提示
The figure of the example:
where D,E,F,GD,E,F,GD,E,F,G are the tangent points given in the input respectively.