Finding the point that maximizes a linear function
Another Answer:

Find the 2D maximal point set. Let us call it the set $M$.
Find the convex hull of $M$. Let us call it $co(M)$.

The preprocessing time for the two step is $O(n \log n)$.
Now, for the line: $c_i \cdot x + y = 0$, you need to find the point in $M$ that is farthest from the line. That point must lie on the boundary of $co(M)$. Note that distances of the points on the convex hull first increase and then decrease. You need to find that point on the boundary where this transition happens. It can be done in $O(\log n)$ time using binary search.