Subtask 1

We can see that the distance squared from a house at ~(x_i, y_i)~ to a point on the ~x~-axis ~(x, 0)~ is ~(x - x_i)^2 + y_i^2~. Since the distance squared to each house is a quadratic in vertex form with a leading coefficient of ~1~, each quadratic is a translation of another. Thus, it must be that each house can be closest to the ~x~-axis over at most one continuous interval. We can keep track of the current left endpoint (starting at ~0~) and binary search for the first value of ~x~ (up to ~X~) which has a different house that is closest to the ~x~-axis at that point. We can do this by looping through each of the ~N~ houses and calculating the distance using the previously given formula. We can then move the left endpoint to that value of ~x~ and repeat. From here, we can compute the required percentage for each house.

There are alternative solutions for this subtask.

Time Complexity: ~\mathcal{O}(N^2 \log X)~

Subtask 2

For the second subtask, we can see that ~h_i~ does not matter. The only part of each house that can be closest to the ~x~-axis is the bottom line segment at ~y = y_i~ where ~x_i \le x \le x_i + w_i~. Unfortunately it is no longer the case that each house can be closest to the ~x~-axis over at most one continuous interval.

On the ~x~-axis, we can see that if ~x \le x_i~, the closest point of the house to the ~x~-axis is ~(x_i, y_i)~. When ~x \ge x_i + w_i~, the closest point of the house to the ~x~-axis is ~(x_i + w_i, y_i)~. When ~x_i \le x \le x_i + w_i~, the closest point of the house to the ~x~-axis is ~(x, y_i)~. Consider all sorted distinct values of ~x_i~ and ~x_i + w_i~. Suppose we have two adjacent values ~l~ and ~r~. In the interval ~[l, r]~ we can see that the equation of distance squared the closest point of each house remains constant. It is either a constant or a quadratic in vertex form with a leading coefficient of ~1~. Thus, within each interval, each house can be closest to the ~x~-axis over at most one continuous segment. We can perform the same algorithm as subtask 1 for each interval. Since the total number of changes of the closest house when moving from ~(0, 0)~ to ~(X, 0)~ is ~\mathcal{O}(N)~, this will not affect the time complexity.

Time Complexity: ~\mathcal{O}(N^2 \log X)~

Subtask 3

If we rearrange the equation of the house to the ~x~-axis to standard form, we obtain ~x^2 - 2 x x_i + x_i^2 + y_i^2~. We can see that each equation has the same quadratic term of ~x^2~. We want to be able to determine for each quadratic, which continuous range of ~x~ values is it the minimum. We can do this by maintaining the convex hull of the quadratics. To simplify this, if we only consider the linear and constant terms, we have the line ~-2 x x_i + x_i^2 + y_i^2~. This does not affect the intersection of the quadratics which is relevant when computing the convex hull. After we compute the convex hull, we can then determine the points of intersection between each pair of adjacent lines in the hull. From these points of intersection, we can determine the ranges where each line is the minimum and compute the percentages from there.

Time Complexity: ~\mathcal{O}(N \log N)~

Subtask 4

Similar to subtask 2, we can consider each house as the two points ~(x_i, y_i)~ and ~(x_i + w_i, y_i)~, and the line at ~y = y_i~. We can compute the convex hull for each of the points and compute the ranges for each quadratic. For each of the lines, we can perform a line sweep to compute a second set of ranges of the closest lines (in terms of distance squared) to the ~x~-axis. We can then combine these ranges using a two pointer approach. For a quadratic and a horizontal line, there could be at most three resulting segments: a segment where the horizontal line is the minimum, a segment where the quadratic is the minimum, and another segment where the line is the minimum. We can compute these segments using the quadratic formula to find the intersection of a horizontal line and a quadratic. After computing the combined range, the percentages can be computed from here.

Time Complexity: ~\mathcal{O}(N \log N)~