关于巧克力蛋糕上樱桃的争论时有发生。每个人都喜欢樱桃,所以必须以每个人都能分到相同数量樱桃的方式来切割蛋糕。
两个人可以用一把简单的刀通过一次直线切割轻松平分蛋糕。虽然不太直观,但两次直线切割总是足以平分给四个人。但如果你想把蛋糕分给三个人呢?我们有一个解决方案!
你得到一个带有樱桃的蛋糕和一把 Y 型刀。请将蛋糕切成三部分,使每部分包含相同数量的樱桃,或者报告这是不可能的。
形式化地,给定平面上处于一般位置的一组点。Y 型刀由一个顶点和从该顶点出发的三条无限长射线组成。任意两条射线之间的夹角等于 $120^\circ$ ($2\pi/3$)。这把刀将平面分成了三个区域。你需要找到顶点的坐标以及第一条射线的旋转角度,使得每个区域包含相同数量的点。
输入格式
输入的第一行包含一个整数 $n$,表示点的数量 ($1 \le n \le 10^5$)。接下来的 $n$ 行,每行包含两个整数 $x$ 和 $y$,表示对应点的坐标。坐标的绝对值不超过 $10^6$。
保证没有两个点重合,且没有三个点在同一条直线上。
输出格式
如果无法实现所需的切割,输出 “No”(不含引号)。
如果可能,输出 “Yes”(不含引号)。然后输出三个实数 $x$、$y$ 和 $r$ ($|x|, |y| \le 10^7$, $0 \le r < 2\pi/3$),其中 $x$ 和 $y$ 表示顶点的坐标,$r$ 表示刀的逆时针旋转角度(以弧度为单位)。
刀的初始位置(即对应零旋转)是其中一条射线指向下方时。射线指向右侧的位置对应于 $\pi/2$ 的旋转。
详细的检查器说明请参阅 “说明” 部分。
样例
输入 1
9 3 -2 -4 6 0 -7 -5 -6 5 1 1 6 -5 0 -3 -7 -4 2
输出 1
Yes -1 0 0.9
说明
所有计算均使用 long double(80 位浮点类型)进行。设顶点为 $(x, y)$,旋转角度为 $r$。对于每个输入点 $(x_i, y_i)$:
- 如果 $|x - x_i| < 10^{-9}$ 且 $|y - y_i| < 10^{-9}$,则判定为 “Wrong Answer”;
- 从顶点指向输入点的方向角计算公式为 $\text{atan2}(y_i - y, x_i - x) + \pi/2 - r \pmod{2\pi}$,其中 $\text{atan2}(y, x)$ 是点 $(x, y)$ 的极角;
- 如果该角度与 $0$、$2\pi/3$ 或 $4\pi/3$ 的绝对差小于 $10^{-9}$,则判定为 “Wrong answer”;
- 最后,直接计算点所属的区域。