Find the maximum of ax+b
Python, 214 bytes

S=sorted
def M(L,X):
 H=[-1,0];R={}
 for a,b in S(L):
    while H[2:]and a*H[-3]+b&gt;H[-2]*H[-3]+H[-1]:H=H[:-3]
    H+=[1.*(H[-1]-b)/(a-H[-2]),a,b]
 for x in S(X):
    while H[2:]and x&gt;H[2]:H=H[3:]
    R[x]=H[0]*x+H[1]
 return R


Computes the convex hull by iterating through the input a,b in increasing a order.  The convex hull is recorded in H using the format -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bn where xi is the x coordinate of the intersection of a{i-1},b{i-1} and ai,bi.

Then I iterate though the input xs in sorted order, truncating the convex hull to keep up as I go.

Everything is linear except for the sorts which are O(n lgn).

Run it like:

&gt;&gt;&gt; print M([[2,8],[4,0],[2,1],[1,10],[3,3],[0,4]], [1,2,3,4,5])
{1: 11, 2: 12, 3: 14, 4: 16, 5: 20}