# How to use convex hull for this problem

Problem:

You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a_i t$ litres of red and $b_i t$ litres of blue liquid. $t$ need not be an integer. At a time you can only do one job. You can choose some (or all) of the jobs and do it for your desired time. Given such $n$ jobs in the input and their respective $a_i$ and $b_i$ find the lowest total time in which you can get $N$ litres of red and $M$ litres of blue liquid.

How do I solve this problem using convex hull?

Perhaps you want a hint first? Of course you start by considering all vectors $(a_i,b_i)$ first. The vector $(a_i,b_i)$ indicates the amounts you earn by working one hour on job $i$.
What is the meaning of any point on the line segment between points $(a_i,b_i)$ and $(a_j,b_j)$?
If any point $(a_k,b_k)$ is within the triangle $(0,0)$, $(a_i,b_i)$, $(a_j,b_j)$ why can you discard it?
• the line segment between points $(a_i,b_i)$ and $(a_j,b_j)$ means in one hour you can get to any point here, but why discard points in the triangle? Dec 25 '15 at 14:55
• Vectors $(a_k,b_k)$ within the triangle (or the convex hull in general) are not efficient enough. Draw a line from origin $(0,0)$ to the vector $(a_k,b_k)$ and find the intersection $I$ with the hull. Then $I$ is reachable in one hour but will in fact give a multiple of liquids compared to $(a_k,b_k)$. Dec 26 '15 at 12:27
• Same idea works when you want to investigate problems that need more than one hour. Scale. Solve the problem with the same $M/N$ proportion but in one hour. Then multiply. Again line through the origin. Dec 26 '15 at 12:31
• so I add points $a_i,b_i$ for all i, find the convex hull and then draw a ray from (0,0) to (N,M). Find its last intersecting point with the hull and that would be the most I can do in an hour. That's it right? Dec 27 '15 at 9:40