题目来源: 2020 CCPC Wannafly 冬令营 Day5: H. Geometry PTSD
题面
在以 \(O\) 为球心的单位球面上寻找三个点 \(A, B, C\), s.t.: \[ \min(|AB|,|BC|,|CA|)\geq1.7 \]
\[ 0<d(O,ABC)\leq10^{-18} \]
输出格式
每行输出三个整数 \(x,y,z\in[-10^{6},10^6]\cap\mathbb Z\), 表示选取了点 \[ \left(\frac{x}{\sqrt{x^2+y^2+z^2}},\frac{y}{\sqrt{x^2+y^2+z^2}},\frac{z}{\sqrt{x^2+y^2+z^2}}\right) \]
题解
设原点为 \(O\). \(A,B,C\) 每个点选取的三个整数分别为 \(\boldsymbol A(A_x, A_y, A_z), \boldsymbol B(B_x, B_y, B_z), \boldsymbol C(C_x, C_y, C_z)\), 记： \[ \left|\boldsymbol P\right|:=\sqrt{P_x^2+P_y^2+P_z^2},\quad\forall \boldsymbol P\in\{\boldsymbol A,\boldsymbol B,\boldsymbol C\} \]
\[ D_0:=\overrightarrow{OA}\times\overrightarrow{OB}\cdot\overrightarrow{OC}=\left| \begin{array}{ccc} \frac{A_x}{|\boldsymbol A|} & \frac{A_y}{|\boldsymbol A|} & \frac{A_z}{|\boldsymbol A|}\\ \frac{B_x}{|\boldsymbol B|} & \frac{B_y}{|\boldsymbol B|} & \frac{B_z}{|\boldsymbol B|}\\ \frac{C_x}{|\boldsymbol C|} & \frac{C_y}{|\boldsymbol C|} & \frac{C_z}{|\boldsymbol C|}\\\end{array} \right| \]
\[ D:= {D_0}{|\boldsymbol A||\boldsymbol B||\boldsymbol C|} = \left| \begin{array} {ccc} A_x & A_y & A_z \\ B_x & B_y & B_z \\ C_x & C_y & C_z \end{array} \right| \]
由三棱锥体积公式，可得： \[ \begin{align} V:=V_{OABC} &=\frac{1}{3}Sh\\ &=\frac{1}{6}|D_0|=\frac{|D|}{6|\boldsymbol A||\boldsymbol B||\boldsymbol C|} \end{align} \]
\[ h=\frac{|D|}{2S|\boldsymbol A||\boldsymbol B||\boldsymbol C|} \]
注意到 \(\sqrt3\approx1.7\), 故尽量选取等边三角形以达到最优。
同时注意到： \[ D= \left| \begin{array} {ccc} 1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & -1 \end{array} \right| \] 满足：\(D=0\), \(|AB|=|BC|=|CA|=\sqrt3\).
同理， \[ D= \left| \begin{array} {ccc} 10^6 & 10^6 & 0 \\ 0 & -10^6 & 10^6 \\ -10^6 & 0 & -10^6 \end{array} \right| \] 有同样的性质，此时： \[ |\boldsymbol A|=|\boldsymbol B|=|\boldsymbol C|=\sqrt2\cdot10^6 \]
\[ h=\frac{|D|}{2S|\boldsymbol A||\boldsymbol B||\boldsymbol C|}=\frac{|D|}{3\sqrt6\cdot10^{18}} \]
微调 \(\boldsymbol A,\boldsymbol B,\boldsymbol C\) , s.t. \(|D|\leq7\) 即可。
打表发现：满足条件的一个 \(D\) 是： \[ D=\left|\begin{array}{ccc}999999 & 10^6 & 0 \\0 & -999999 & 999997 \\-999997 & 0 & -999996\end{array}\right|=-4 \]
\[ h=\frac{|D|}{2S|\boldsymbol A||\boldsymbol B||\boldsymbol C|}\approx\frac{4}{3\sqrt6\cdot10^{18}}<10^{-18} \]