Subtask 1

For subtask 1, note that if our line has slope-intercept form ~y = mx+b~ after rotating the plane, then the balance value is equal to

$$\displaystyle \left|\sum_{i=1}^n y_i-(mx_i+b)\right| = \left|\left(\sum_{i=1}^n y_i\right)-m\left(\sum_{i=1}^n x_i\right)-bN\right|$$

where ~(x_i,y_i)~ are the rotated points. Thus if we precompute the sum of the ~x_i~'s and the sum of the ~y_i~'s, then we can evaluate the balance value of any line in ~\mathcal{O}(1)~. We can now check all pairs of points for each query and take the smallest balance value.

Time complexity: ~\mathcal{O}(QN^2)~

Subtask 2

For subtask 2, note that we can rearrange the balance value to

$$\displaystyle N\left|\left(\frac{\sum_{i=1}^n y_i}{N}\right)-m\left(\frac{\sum_{i=1}^n x_i}{N}\right)-b\right|$$

which is equal to ~N~ times the vertical distance from the centroid of the ~N~ points to the line. We can now visualize each query as drawing two rays coming out of the centroid at directions ~(-b_i,a_i)~ and ~(b_i,-a_i)~, and we want to know the first time one of these two rays hits a line formed by two of the ~N~ points.

Consider fixing one of the points ~p~ on the optimal line. Then the lines formed by ~p~ and one of the other points cut the plane into several pieces, and the centroid must lie in one of them. We can see that only the two lines that border this piece might be the optimal line. We can find these two candidate lines by looping through the other ~N-1~ points and taking the two with the closest slope to ~p~ as the centroid. Now we have only ~\mathcal{O}(N)~ lines to check for each query, which can be done in ~\mathcal{O}(QN)~ total.

Be careful to handle the corner case where the centroid lies on a line that becomes vertical after rotation, as in sample 2.

Time complexity: ~\mathcal{O}(N^2+QN)~

Subtask 3

For subtask 3, we need to do better than linear time for each query. Note that the ~\mathcal{O}(N^2)~ lines cut the plane into several convex regions. We can find the border of the region containing the centroid with a "circular" convex hull trick and then process all the queries with an angular sweep through the convex hull.

Again, be careful to handle the corner case where the centroid lies on a line that becomes vertical after rotation, as in sample 2.

Time complexity: ~\mathcal{O}(N^2\log N+Q\log Q)~

Subtask 4

For subtask 4, we need to do better than looping through all pairs of the ~N~ points. Consider sorting the ~N~ points by their slope around the centroid. Then it can be shown that the optimal line is one of the ~N~ pairs of adjacent points in this ordering (including the pair formed by the first and last point). Thus we can obtain ~\mathcal{O}(N)~ candidate lines by sorting the points once, and we can try all of them for each query.

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

Subtask 5

For subtask 5, we can combine the ideas in subtasks 3 and 4 to build the circular hull from the ~\mathcal{O}(N)~ candidate lines.

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