← All solutions

Shortest judge solution: 3195 bytes. Shortest team solution (during contest): 5540 bytes.

This problem is a geometry problem in disguise. For each person i, let us view (a_i, b_i) as the Cartesian coordinates of a 2-dimensional point. We then have two (multi-)sets of points P₁ (the set of people with c_i = 1) and P₀ (the set of people with c_i = 0).

For a choice of the parameters S and T, the set of points (a_i, b_i) with S · a_i + T · b_i = v for some v forms a line in the plane, with (S, T) as the normal vector. This means that the points that fall in between the first and the last point from P₁ are those which are contained in a stripe between the two tangents of the convex hull of P₁ with direction (−T, S) (including points exactly on the tangents).

Here is an illustration of a small case, where the green points represent P₁ (which happen to form a circle in this test case), the dashed black lines are the two tangents with direction (−T, S) in the optimal solution, the red points are the points of P₀, and the red points with a blue dot in them are the points in P₀ that fall inside the stripe.

In order to find the best possible (S, T), we have to try rotating the tangents and keep track of how many points from P₀ fall between them. The only time a count changes is when one of the two tangents hits a point from P₀. Since we only care about the convex hull of P₁, we can find the tangents from any point q to the hull of P₁ in O(log n) time using binary search – this is needed since there can be a lot of points. Once we have all the tangents, we can apply the sweep-line methodology to try all relevant rotations in O(n log n) time.

There was one very tricky special case, which is the case when |P₁| = 1. In this case the answer is always 1, even if there are points from P₀ that coincide with the point in P₁. Since the judges are such nice and friendly people, this special case was included in the sample data. In addition to this, usual geometry caveats with collinear and duplicate points apply.