Subtask 1

In this subtask, we simply need to consider the concert point with the minimal ~y~-value. Let this value be ~a~. To be closer to the concession stand compared to the concert, all points in the rectangle need to be on or below the line ~y = \lfloor \frac{a-1}{2} \rfloor~, and the answer can be derived as ~\binom{\lfloor{\frac{a-1}{2}}\rfloor+1}{2}~. Note that since the first point given in the input will always have the minimal ~y~-value, we do not even need to fully read the input.

Time complexity: ~\mathcal{O}(1)~

Subtask 2

We now restate the problem into finding the total number of rectangles within a bounding box such that each point within the rectangle is closer to a line compared to a point. Notice that this condition is quite related to the conic definition of a parabola (the locus of all points that are equidistant to a directrix and focus).

Using this idea, we can convert each pair of line and point to a parabola. Then, the answer to the problem is the number of rectangles that fit completely below all parabolas. We can derive the equation of a parabola with a line ~y = a~ and point ~(h, k)~ as:

$$\displaystyle y = \frac{(x-h)^2}{2(k-a)}+k$$

In this subtask, all shifts are vertical. Thus, it suffices to only consider the lowest parabola (the first one given in input). To determine the answer, we can do some clever counting. One such method would be to start counting from the middle of the parabola and "move outwards".

Time complexity: ~\mathcal{O}(W)~

Subtask 3

Now, we need to handle multiple parabolas. It is clear that we need to determine the quadratic function with the minimal value for all integer values of ~x \in [0, W]~. In this subtask, it suffices to iterate over all functions to determine the minimal value for each value of ~x~.

Afterwards, we need a different method to count the number of rectangles under all parabolas. We can convert this subproblem into finding the maximum number of rectangles in a histogram, which can be solved using stacks or disjoint set union. The implementation details are left as an exercise to the reader.

Time complexity: ~\mathcal{O}(NW)~

Subtask 4

The bottleneck of our solution in subtask 3 lies in finding the quadratic function with the minimal value for all integer values of ~x \in [0, W]~. To optimize, notice that since the distance between each pair of line and point remains unchanged, each quadratic function has the same coefficient for the quadratic term. Thus, we can ignore this term when finding the minimal function at any value of ~x~.

Now, we are left with finding the minimal value at different values of ~x~ over a set of linear functions, which can be efficiently done with CHT.

Time complexity: ~\mathcal{O}(W + N \log N)~