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?


1 Answer 1


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?

  • $\begingroup$ 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? $\endgroup$
    – e_noether
    Dec 25, 2015 at 14:55
  • $\begingroup$ how do I find what I can do in two hours or more? $\endgroup$
    – e_noether
    Dec 26, 2015 at 8:41
  • $\begingroup$ 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)$. $\endgroup$ Dec 26, 2015 at 12:27
  • $\begingroup$ 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. $\endgroup$ Dec 26, 2015 at 12:31
  • $\begingroup$ 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? $\endgroup$
    – e_noether
    Dec 27, 2015 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.