/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
以下の条件を全て満たす xy 平面上の三角形 ABC を良い三角形とします。
- 頂点 A,B,C はいずれも、x 座標 \cdot y 座標がどちらも 0 以上 10^{8} 以下の格子点である。
- 全ての頂点が格子点である面積 1 の正方形のうち、三角形 ABC の内部 (周上及び頂点を含む) に全体が含まれているものはちょうど 1 つ
正の整数 S が与えられます。
良い三角形のうち面積が \frac{S}{2} であるものが存在するか判定し、存在するなら 1 つ構築してください。
1 つの入力ファイルにつき 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
出力
各ケースに対し、面積 \frac{S}{2} の良い三角形が存在しない場合は No と、存在する場合は以下の形式で答えを出力してください。
Yes AX AY BX BY CX CY
ただし、 AX,BX,CX を A,B,C の x 座標、 AY,BY,CY を A,B,C の y 座標とします。
Yes, No を出力する際、各文字は英大文字・小文字のいずれでも良いです。
解が複数存在する場合はどれを出力しても正解とみなされます。
入力例 1
3 1 4 15
出力例 1
No Yes 1 1 1 3 3 3 Yes 5 1 7 8 4 5
図の左側の三角形は 2 番目のテストケース、右側の三角形は 3 番目のテストケースに対応しています。
Score : 800 points
Problem Statement
A triangle ABC on the xy-plane is said to be a good triangle when it satisfies all of the following conditions.
- Each of the vertices A, B, and C is a lattice point whose x- and y-coordinates are between 0 and 10^{8}, inclusive.
- The triangle ABC (including the perimeter and vertices) wholly contains exactly one square of area 1 whose vertices are all lattice points.
You are given a positive integer S.
Determine if there is a good triangle of area \frac{S}{2}, and construct one if it exists.
For each input file, you have T test cases to solve.
Constraints
- 1\leq T\leq 10^{5}
- 1\leq S\leq 10^{8}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}
Each case is given in the following format:
S
Output
For each case, print No if there is no good triangle of area \frac{S}{2}, and such a triangle in the following format if there is one.
Yes AX AY BX BY CX CY
Here, AX, BX, CX are the x-coordinates of A, B, C, and AY, BY, CY are the y-coordinates of A, B, C, respectively.
When printing Yes or No, you may use either uppercase or lowercase English letters.
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 1 4 15
Sample Output 1
No Yes 1 1 1 3 3 3 Yes 5 1 7 8 4 5
In the figure, the left and right triangles correspond to the second and third test cases, respectively.