QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

#685. Y形刀

Statistics

关于巧克力蛋糕上樱桃的争论时有发生。每个人都喜欢樱桃,所以必须以每个人都能分到相同数量樱桃的方式来切割蛋糕。

两个人可以用一把简单的刀通过一次直线切割轻松平分蛋糕。虽然不太直观,但两次直线切割总是足以平分给四个人。但如果你想把蛋糕分给三个人呢?我们有一个解决方案!

你得到一个带有樱桃的蛋糕和一把 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”;
  • 最后,直接计算点所属的区域。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.