分数: 800 点
问题陈述
一个三角形 ABC 上 xy- 当满足以下所有条件时,平面被认为是一个好的三角形。
- 每个顶点 A, B,和 C 是一个格点,其 x- 和 y- 坐标介于 0 和 10^{8},包括在内。
- 三角形 ABC (包括 周长和顶点)完全包含一平方面积 1 ,其顶点都是格点。
给你一个正整数 S.
判断是否存在好的三角形面积 \frac{S}{2},并构造一个(如果存在)。
对于每个输入文件,您有 T 测试用例解决。
约束
- 1\leq T\leq 10^{5}
- 1\leq S\leq 10^{8}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}
每个案例均按以下格式给出:
S
输出
对于每种情况,打印 No 如果没有好的三角形面积 \frac{S}{2},如果有一个这样的三角形,其格式如下。
Yes AX AY BX BY CX CY
在这里, AX, BX, CX 是 x- 坐标 A, B, C,和 AY, BY, CY 是 y- 坐标 A, B, C。
打印时 Yes or No,您可以使用大写或小写英文字母。
如果存在多个解决方案,则其中任何一个都将被接受。
样本输入 1
3 1 4 15
示例输出 1
No Yes 1 1 1 3 3 3 Yes 5 1 7 8 4 5

图中,左右三角形分别对应第二个和第三个测试用例。