## Editorial for Wesley's Anger Contest 6 Problem 7 - SantaTracker++

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

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

There are alternative solutions for this subtask.

Time Complexity:

For the second subtask, we can see that does not matter. The only part of each house that can be closest to the -axis is the bottom line segment at where . Unfortunately it is no longer the case that each house can be closest to the -axis over at most one continuous interval.

On the -axis, we can see that if , the closest point of the house to the -axis is . When , the closest point of the house to the -axis is . When , the closest point of the house to the -axis is . Consider all sorted distinct values of and . Suppose we have two adjacent values and . In the interval 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 . Thus, within each interval, each house can be closest to the -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 to is , this will not affect the time complexity.

Time Complexity:

If we rearrange the equation of the house to the -axis to standard form, we obtain . We can see that each equation has the same quadratic term of . We want to be able to determine for each quadratic, which continuous range of 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 . 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: