#P17996. Euler Line

Euler Line

Euler Line

题目描述

给定平面上的一条直线,构造一个顶点均为整数坐标的非退化三角形,使它的欧拉线恰好是给定直线;如果无法构造,则报告无解。

对于非退化三角形 ABCABC:

  • 外心 OO:三边垂直平分线的交点,也是经过三个顶点的外接圆圆心。
  • 垂心 HH:三条高所在直线的交点。钝角三角形中可以位于高的延长线上。
  • 重心 GG:三条中线的交点。
  • 九点圆圆心 O9O_9:三边中点所成三角形的外心。这个圆还经过三条高的垂足,以及 AH,BH,CHAH,BH,CH 的中点。

非等边三角形中,这四点互不相同且共线,所在直线称为三角形的欧拉线。O9O_9 是 OHOH 的中点,GG 在线段 OHOH 上且 OG:GH=1:2OG:GH=1:2。等边三角形中四点重合,但非退化的整数坐标等边三角形不存在,因此无须额外排除等边情形。

输入格式

第一行一个整数 tt,表示测试用例数,1≤t≤5×1051\le t\le5\times10^5。

每组一行三个整数 k,ℓ,mk,\ell,m,表示直线

kx+ℓy+m=0.kx+\ell y+m=0.

满足 −1000≤k,ℓ,m≤1000-1000\le k,\ell,m\le1000,并且 k2+ℓ2>0k^2+\ell^2>0。

输出格式

每组输出六个整数 Ax,Ay,Bx,By,Cx,CyA_x,A_y,B_x,B_y,C_x,C_y,表示三角形的三个顶点。坐标都必须属于 [−106,106][-10^6,10^6],且三角形非退化,欧拉线恰为输入直线。可以输出任意合法方案。

若无解,输出六个 00。

保证如果存在整数坐标解,则也存在满足上述坐标范围的解。

样例 1

输入

8
0 1 0
1 0 1
-1 1 -2
3 4 8
1 1 1
8 4 2
27 9 3
-544 862 12

输出

-1 -1 -1 1 0 0
-2 -2 -2 2 1 -1
-2 -1 -2 2 0 1
-4 -3 2 -4 2 1
-1 -1 -1 0 0 0
0 0 0 0 0 0
-4 0 3 -2 0 4
5811 -1154 -3261 -2058 -3713 2478