#P17889. Infrared

Infrared

给定一个按逆时针顺序列出顶点的严格凸多边形 p1,p2,…,pnp_1,p_2,\ldots,p_n。第 ii 面墙是边 [pi,pi+1][p_i,p_{i+1}],其中 pn+1=p1p_{n+1}=p_1。

从顶点 p1p_1 发射激光,希望它依次在第 2,3,…,n−12,3,\ldots,n-1 面墙上反射,最后回到 p1p_1。反射遵循入射角等于反射角的规律。

每次反射必须发生在边的内部,并与两端点保持足够距离:若反射点为 αa+(1−α)b\alpha a+(1-\alpha)b,则

min⁡(α,1−α)≥10−5.\min(\alpha,1-\alpha)\ge10^{-5}.

判断是否存在符合要求的发射方向。如果存在,输出角度。正 xx 轴对应 00 度,逆时针为正方向。

输入格式

第一行测试用例数 tt,1≤t≤10001\le t\le1000。

每组先输入 nn,3≤n≤203\le n\le20。接着 nn 行各输入两个整数 xi,yix_i,y_i,−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9。

保证顶点逆时针排列且构成严格凸多边形。

为排除数值临界情况,数据还保证:有解时存在一个方向使所有反射点满足 min⁡(α,1−α)≥10−5+10−9\min(\alpha,1-\alpha)\ge10^{-5}+10^{-9};无解时,不存在几乎合法的方向,即必定出现没有交点,或某次反射满足 min⁡(α,1−α)<10−5−10−9\min(\alpha,1-\alpha)<10^{-5}-10^{-9}。

输出格式

无解时输出一行 NO。

有解时输出一行 YES,下一行输出实数角度 dd,−180≤d≤180-180\le d\le180。

输出方向必须使光线按指定顺序击中所有指定墙面内部,并最终到达 p1p_1 的允许误差范围。设多边形周长为 LL,最终在第 11 或第 nn 面墙上的交点 (x,y)(x,y) 需满足

(x−x1)2+(y−y1)2<(10−7L)2.(x-x_1)^2+(y-y_1)^2<(10^{-7}L)^2.

若有多个合法角度,输出任意一个。

样例

2
3
1 2
0 0
2 0
4
0 0
1 0
1 1
0 1
YES
-90
NO
3
4
0 0
4 0
5 4
-1 4
5
-809016994 -587785252
309016994 -951056516
1000000000 0
309016994 951056516
-809016994 587785252
6
-1000000000 0
-500000000 -866025404
500000000 -866025404
1000000000 0
500000000 866025404
-500000000 866025404
YES
24.623564786163612980174342226292
YES
9.732301397707778775440778940009
NO