P4490 [CTSC2009] Magic Garden

Wizard Dongdong has a beautiful magic garden filled with all kinds of magical plants, blooming with colorful flowers throughout the year. Dongdong’s friends love to come and play in the garden. The garden’s irrigation system is specially designed by Dongdong. He used magic to create $n$ sprinklers suspended over the garden, all connected to the nearby Holy Water River. When irrigating, all sprinklers simultaneously eject streams of water. The water traces beautiful arcs in the air and lands precisely on the $n$ most water-starved magical plants.  Dongdong placed every sprinkler at the same height $h$. All sprinklers are oriented horizontally, so when water is ejected, it has only horizontal velocity (the horizontal velocity may differ between sprinklers). There is no wind in the magic garden, and air resistance is negligible. Therefore, under gravity (the gravitational acceleration in the magic garden is $g$), the water follows perfect parabolic trajectories. Any point in space is reached by water from at most three sprinklers, and intersections of water streams do not affect their trajectories. In recent years, many factories have been built near the magic garden, and the Holy Water River has become polluted. Dongdong does not want polluted water to affect his garden, so he intends to purify the irrigation water using magic. His magic can only purify water as it leaves the sprinklers. He can cast a spell to create a convex polygon filter layer lying in some horizontal plane in the air. All water passing through this filter layer will be purified. The energy required to cast this spell is proportional to the area of the filter layer: each square meter of filter layer requires $1$ unit of magical energy. Dongdong wants to purify all the water. What is the minimum energy he needs? To better describe the problem, Dongdong sets up a 3D Cartesian coordinate system in the garden with the northwest corner as the origin. The positive $x$-axis points east, the positive $y$-axis points south, and the positive $z$-axis points upward. Thus the position of the $i$-th sprinkler is $(x_i, y_i, h)$, and the position of the $j$-th magical plant is $(x_j', y_j', 0)$.

The first line contains two real numbers $h, g$, representing the sprinklers’ height and the gravitational acceleration in the magic garden. The second line contains an integer $n$, the number of sprinklers. Each of the next $n$ lines contains four integers $x_i, y_i, x_i', y_i'$, separated by a space. This means the $i$-th sprinkler is at $(x_i, y_i, h)$, and its water lands exactly on the magical plant at $(x_i', y_i', 0)$.

Output a single real number: the minimum energy required by Dongdong, accurate to at least 3 decimal places.

【Sample Explanation 1】 If the magic is cast at height $35$, all water streams converge at the point $(100, 100, 35)$, so the required energy is $0$. 【Sample Explanation 2】 If the magic is cast at height $10$ (i.e., at the sprinklers), the magic forms a right triangle with vertices $(0, 0, 10)$, $(1, 0, 10)$, and $(0, 50, 10)$. Its area is $25.000$, so the required magical energy is also $25.000$. 【Scoring】 For each test point, if your answer differs from the standard answer by no more than $0.001$, you receive full score for that test point; if the difference is greater than $0.001$ but no more than $0.002$, you receive 50% of the score; otherwise, you receive 0. 【Constraints】 - For 20% of the testdata, $1 \leq n \leq 10$. - For 50% of the testdata, $1 \leq n \leq 50$. - For 100% of the testdata, $1 \leq n \leq 100$. - $0 < h \leq 10000.0$. - $0 < g \leq 100.0$. - $0 \leq x_i, y_i, x_i', y_i' \leq 1000$. 【Tips】 The motion of water from the sprinkler to the ground can be regarded as horizontal projectile motion. It can be decomposed into two component motions along the horizontal and vertical directions. Let $L = (x_i - x_i')^2 + (y_i - y_i')^2$. Then: Initial speed: $v_0 = \sqrt{\frac{Lg}{2h}}$. Horizontal component of velocity at time $t$: $v_{\text{平}}(t) = v_0$. Vertical component of velocity at time $t$: $v_{\text{竖}}(t) = gt$. Speed at time $t$: $v(t) = \sqrt{v_{\text{平}}^2(t) + v_{\text{竖}}^2(t)}$. Translated by ChatGPT 5