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.