雾之湖直角三角形 - 寻找第三个点

在雾之湖的网格图上，给定两个点的坐标，寻找第三个点，使得这三个点可以构成直角三角形。//////n/////n题目描述//////n/////n雾之湖可以被看成一张巨大网格图，图上所有点的坐标均为整数，并且 //$x,y//$ 坐标的范围均为 //$[-10^9,10^9]//$。琪露诺在其中发现两块奇怪的石头，它们的坐标分别记为 //$A,B//$。你需要找到网格图上的第三个点 //$C//$，使得 //$ABC//$ 三点可以构成直角三角形。如果有多解，输出任意一组即可。//////n/////n注意：由于 //$C//$ 在网格图上，因此 //$C//$ 的坐标同样必须是整数。//////n/////n//////n/////n如图所示，//$A,B//$ 的坐标分别为 //$(0,0)//$ 和 //$(4,2)//$。图中给出了三个可能的 //$C//$：//////n/////n- //$C_1//$ 坐标为 //$(1,3)//$，组成橙色的三角形，//$∠AC_1B=90/degree//$。//////n- //$C_2//$ 坐标为 //$(-1,2)//$，组成黄色的三角形，//$∠C_2AB=90/degree//$。//////n- //$C_3//$ 坐标为 //$(5,0)//$，组成红色的三角形，//$∠ABC_3=90/degree//$。//////n/////n数据保证输入的 //$A,B//$ 不会重合。//////n/////n输入格式//////n/////n共一行，四个整数 //$x_1,y_1,x_2,y_2//$，表示 //$A,B//$ 的坐标 //$(x_1,y_1),(x_2,y_2)//$。//////n/////n输出格式//////n/////n共一行，两个整数 //$x_3,y_3//$，表示你找到的点 //$C//$ 的坐标。你需要保证 //$0/le |x_3|,|y_3|/le 10^9//$。若有多解输出任意一组即可。//////n/////n样例 #1//////n/////n### 样例输入 #1//////n/////n//////n0 0 4 2//////n//////n/////n### 样例输出 #1//////n/////n//////n1 3//////n//////n/////n提示//////n/////n### 数据范围及约定//////n/////n- 对于 //$30/%//$ 的数据，保证 //$0/le |x_1|,|y_1|,|x_2|,|y_2|/le 2//$。//////n- 对于 //$50/%//$ 的数据，保证 //$0/le |x_1|,|y_1|,|x_2|,|y_2|/le 10//$。//////n- 对于 //$70/%//$ 的数据，保证 //$0/le |x_1|,|y_1|,|x_2|,|y_2|/le 10^3//$。//////n- 对于全部数据，保证 //$0/le |x_1|,|y_1|,|x_2|,|y_2|/le 10^9//$，并且 //$A,B//$ 两点不会重叠。//////n/////n解题思路//////n/////n根据直角三角形的性质，我们可以得到以下三个方程：//////n/////n$$//////n//begin{cases}////n(x_3-x_1)(x_3-x_2)+(y_3-y_1)(y_3-y_2)=0 ////n(x_1-x_3)^2+(y_1-y_3)^2=(x_2-x_3)^2+(y_2-y_3)^2 ////n(x_1-x_2)^2+(y_1-y_2)^2=(x_1-x_3)^2+(y_1-y_3)^2+(x_2-x_3)^2+(y_2-y_3)^2//////n//end{cases}////n$$//////n/////n我们可以将这个方程组转化为以下形式：//////n/////n$$//////n//begin{cases}////n(x_3-x_1)(x_3-x_2)+(y_3-y_1)(y_3-y_2)=0 ////n(x_3-x_1)^2+(y_3-y_1)^2-(x_3-x_2)^2-(y_3-y_2)^2=0 ////n(x_1-x_2)^2+(y_1-y_2)^2-(x_1-x_3)^2-(y_1-y_3)^2-(x_2-x_3)^2-(y_2-y_3)^2=0//////n//end{cases}////n$$//////n/////n我们可以将这个方程组化简为以下形式：//////n/////n$$//////n//begin{cases}////n2(x_3^2-x_1x_2+y_3^2-y_1y_2)=x_1^2-x_2^2+y_1^2-y_2^2 ////n2(x_3x_1-x_3x_2+y_3y_1-y_3y_2)=x_3^2-x_1^2+y_3^2-y_1^2 ////n2(x_2x_1+y_2y_1-x_3x_1-y_3y_1-x_2x_3-y_2y_3)=x_1^2+x_2^2+y_1^2+y_2^2-x_3^2-y_3^2//////n//end{cases}////n$$//////n/////n解这个方程组，可以得到点 //$C//$ 的坐标 //$(x_3,y_3)//$。