← 返回题目列表

AtCoder · arc167_e

E. 三角形中的一个正方形

中文机器翻译题面 查看原题

分数: 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

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