Alternate Solution to Square Locator (Universal Cup Season 3 Stage 6)

Problem Link: QOJ9168

Solution

We get $A_y = AO$ because $A$ is on the positive $y$-axis.

Next, let’s represent points $B$ and $C$ in terms of $D_x$, $D_y$, and $A_y$.

Rotating point $D$ by $90^\circ$ clockwise about $A$ gives us

\[\begin{align*} B_x &= D_y - A_y, \\ B_y &= A_y - D_x. \\ \end{align*}\]

Rotating point $A$ by $90^\circ$ counterclockwise about $D$ gives us

\[\begin{align*} C_x &= D_x + D_y - A_y, \\ C_y &= D_y - D_x. \\ \end{align*}\]

Now, let’s solve for $D_x$ and $D_y$. To do this, we set up two equations using the distances we have. Our first equation is

\[\begin{align*} D_x^2 + D_y^2 &= DO^2. \\ \end{align*}\]

For our second equation, we can choose whether to use $BO$ or $CO$. During the contest, I used $CO$, so that’s what I will use here.

We start with

\[C_x^2 + C_y^2 = CO^2.\]

Substituting $C_x = D_x + D_y - A_y$ and $C_y = D_y - D_x$ gives us

\[(D_x + D_y - A_y)^2 + (D_y - D_x)^2 = CO^2.\]

We expand and simplify to get

\[\begin{align*} \left(D_x^2 + D_y^2 + A_y^2 + 2D_xD_y - 2(D_x + D_y)A_y\right) + (D_x^2 + D_y^2 - 2D_xD_y) &= CO^2, \\ 2\left(D_x^2 + D_y^2\right) + A_y^2 - 2(D_x + D_y)A_y &= CO^2. \end{align*}\]

Sbustituting $D_x^2 + D_y^2 = DO^2$ and solving for $D_x + D_y$ gives us

\[\begin{align*} 2DO^2 + A_y^2 - 2(D_x + D_y)A_y &= CO^2, \\ 2(D_x + D_y)A_y &= 2DO^2 + A_y^2 - CO^2, \\ D_x + D_y &= \frac{2DO^2 + A_y^2 - CO^2}{2A_y}. \\ \end{align*}\]

Let’s set

\[V = \frac{2DO^2 + A_y^2 - CO^2}{2A_y}.\]

Substituting $V$ into our current equation and solving for $D_y$, we get

\[\begin{align*} D_x + D_y &= V, \\ D_x &= V - D_y. \\ \end{align*}\]

Substituting into $D_x^2 + D_y^2 = DO^2$ gives us

\[D_x^2 + \left(V - D_x\right)^2 = DO^2.\]

Expanding and converting to a standard form quadratic equation gives us

\[\begin{align*} D_x^2 + \left(V^2 - 2VD_x + D_x^2\right) &= DO^2, \\ 2D_x^2 - 2VD_x + \left(V^2 - DO^2\right) &= 0. \\ \end{align*}\]

Applying the quadratic formula gives us

\[D_x = \frac{2V \pm \sqrt{4V^2 - 8\left(V^2 - DO^2\right)}}{4}.\]

Use one solution for $D_x$ and the other for $D_y$. Either order works. Then, use the transformations from earlier to solve for points $B$ and $C$.

Implementation Tips

Note that $A_y$, $B_x$, $B_y$, $C_x$, $C_y$, $D_x$, and $D_y$ are all integers. Therefore, you don’t have to use floating points for calculations. The intermediate calculation of $V$ is also an integer since $D_x + D_y$ is an integer.

However, you need to be careful of integer overflow, since the input can be up to $10^{18}$. Therefore, it is beneficial to use Python, where no integer overflow exists. Recent versions of Python have math.isqrt, which computes the integer square root, so you don’t have to write a binary search for square root calculations.

Code

import math

a, b, c, d = map(int, input().split())
ay = math.isqrt(a)
v = (2 * d + ay * ay - c) // (2 * ay)
dx = (2 * v - math.isqrt(4 * v * v - 8 * (v * v - d))) // 4
dy = (2 * v + math.isqrt(4 * v * v - 8 * (v * v - d))) // 4
cx = dx + dy - ay
cy = dy - dx
bx = dy - ay
by = ay - dx

print(ay, bx, by, cx, cy, dx, dy)