Auto comment: topic has been updated by unknown_b (previous revision, new revision, compare).

if anyone wants to submit there is a group for past ACPC contests and many other regional contests.

https://codeforces.net/group/Rilx5irOux/join .

Go for contest ACPC 2020 problem B Please.

I'm also eager to find out the solution

yes

.

I finally solved this!!

Thank you ademby for helping solve this problem.

Here is a link to the submission (you should be a member of the group in order to access it).

Thoughts:

A few definitions first. Let's call the point at the midpoint of the board $$$M$$$, the intersection of the board and the hoop $$$I$$$, the other endpoints of the board and the hoop, respectively, $$$B$$$ and $$$H$$$.

I'm going to define a function for the hoop, the board, the tangent of the parabola at the midpoint of the board (this is useful for dealing with the angle $$$\alpha$$$), and the trajectory of the ball after hitting the board.

Let $$$X = L + \frac{D}{2} \sin(\theta)$$$. This is the x-coordinate of $$$M$$$.
Let $$$Y = y + \frac{D}{2} \cos(\theta)$$$. This is the y-coordinate of $$$M$$$.

This is a bit harder to define. So, I'm just going to assume that we know the angle $\gamma$ that the trajectory of the ball makes with the horizontal axis. If it turns out we actually need this, we will try to write $$$\gamma$$$ in terms of other variables we already know.

We may or may not use these definitions in the actual solution; it's just a good start to understand more about the problem.

It is obvious that solving this problem visually is challenging. Try changing the value of $$$\theta$$$ a few times and experimenting with a few shapes for the parabola (it can also be a straight line for $$$A = 0$$$). So, we will have to convert the problem to a system of equations and solve it (kind of).

But we can still extract a few observations visually.

1. The ball has to come from the left of the board and not from its right (otherwise, the ball bounces outwards and does not go through the hoop).

2. The angle $$$\alpha$$$ must follow $$$0 < \alpha < \frac{\pi}{2}$$$ (otherwise, the ball bounces outwards and does not go through the hoop).
   We can further constrain $$$\alpha$$$. Consider the triangle $$$HMI$$$ and specifically the angle $$$\angle HMI$$$. We can see that in order for the ball to go through the hoop, the angle $$$\alpha$$$ must be no more than $$$\arctan\left(\tan(\angle HMI)\right) = \arctan\left(\frac{D}{D/2}\right) = \arctan(2)$$$. So, $$$\alpha$$$ must follow: $$$0 < \alpha < \arctan(2)$$$ (We use strict inequalities as the ball cannot go through the endpoints of the hoop).

3. We can also observe that for a fixed $$$\theta$$$, there is a single value of $$$y$$$ that satisfies the intersection of the parabola and the board at $$$M$$$. So, we should be able to deduce the value of $$$y$$$ if we know the value of $$$\theta$$$.

Up until now, we have an inequality on the value of $$$\alpha$$$ and an equality on the value of $$$y$$$. In general, in order to solve for two unknown variables ($$$\theta$$$ and $$$y$$$), we need at least two equalities. With what we have, we can hope to iterate the possible values of one of the variables (by using the range of the inequality) using a step that is smaller than the given precision.

Let's try to add some math to what we discovered.

1. The first relationship is a classical problem in geometry. Try this similar problem to familiarize yourself: CSES — Point Test Location. In order to formalize the first relationship, let us look at the vector $$$\overrightarrow{MB}$$$ and the directional vector of the tangent of the parabola at $$$M$$$, $$$\overrightarrow{v}$$$:

We will use the cross product to make sure that vector $$$\overrightarrow{v}$$$ is always on the right of vector $$$\overrightarrow{MB}$$$:

1. To ensure that $\alpha$ stays in $$$]0, \pi/2[$$$, we can use the dot product of $$$\overrightarrow{MB}$$$ and $$$-\overrightarrow{v}$$$:

To ensure that $\alpha$ stays in $$$]0, \arctan(2)[$$$, we can use the cross product of $$$\overrightarrow{MB}$$$ and $$$-\overrightarrow{v}$$$ to get the value of $$$\sin(\alpha)$$$:

1. The intersection of the parabola and the board gives:

Okay, we are almost done. We have to read the statement carefully and see that only positive values of $y$ are accepted ($$$y > 0$$$). We should also make sure that the value of $$$X$$$ stays positive, as the player who shoots the ball is at $$$(0, 0)$$$. It does not make sense for the ball to be thrown to the right and then hit the board at a negative x-coordinate.

Nice! Now, if we iterate over all values of $$$\theta$$$ from $$$-\pi/3$$$ to $$$\pi/3$$$ with a step equal to $$$10^{-5}$$$ (to be extra sure), and check each time if a value meets the constraints, we can get the answer in $$$\frac{2\pi}{3} \cdot 10^5$$$ operations, theoretically.

Of course, this wouldn't be a geometry problem without precision issues. The conditions heavily rely on trigonometric functions. We should be able to make a few adjustments so that we use these functions only once (or as minimum as possible). Here are the final conditions:

We can find mathematically the exact value of

Let

.

Next, we can make a few changes so that MB, v and y only rely on the value of $X$. This limits the use of trigonometric functions to once: $$$\sin(\theta)$$$.

Next, instead of thinking in terms of $\theta$, we can iterate through the possible values of $$$X$$$ as everything depends on $$$X$$$. The value of $$$X$$$ should be in: $$$\left[\max(0, L - \frac{D}{2}), L + \frac{D}{2}\right]$$$.

We have to add another check though, the value of $$$\theta$$$ should be in: $$$\left[-\pi/3, \pi/3\right]$$$. We know that the value of $$$sin(\theta) = 2(X-L)/D$$$. So we can simply check if $$$2(X-L)/D$$$ is in $$$\left[-\sqrt{3}/2, \sqrt{3}/2\right]$$$ or not.

We know that $$$0 < D < 100$$$. So, we would make a total of $$$10^5 \cdot 100$$$ operations for a precision value set to $$$10^{-5}$$$ on each test case (yes, it is annoying that we don't know the number of test cases). The only way to know if the solution works is by submitting and adjusting the precision value. We tried $$$10^{-5}$$$, and it worked.

For those wondering why we are using the precision value of the angle $$$\alpha$$$ as the precision value for $$$X$$$ (they aren't necessarily the same), we assumed that a small change in the value of $$$\alpha$$$ will generate a proportional small change of the value of X.

ademby and I tried to minimize precision errors as much as possible. We don't actually know where (along these techniques) the solution breaks or if they are all required or not.