StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This problem falls into the category of <strong>Integer Convex Optimization</strong>. </p> <p>Presented here is a mathematical way to approach the problem. I don't expect you to actually use it - a lot of complicated techniques are required, and other algorithmic approaches (such as "searching" for the appropriate point) will likely do just fine. However, interest has been expressed in the "true" solution, so here it is.</p> <p>It can be solved in three stages:</p> <ol> <li>First, determine which side of each line the answer will be on, as illustrated by TheMachineCharmer's answer. </li> <li>Once that is known, the problem can be rewritten as a convex optimization problem (see <a href="http://en.wikipedia.org/wiki/Convex_optimization" rel="nofollow noreferrer">Wikipedia</a> for details). The function to be optimized is minimizing (x - x0)^2 + (y - y0)^2, with x0 and y0 the coordinates of the intersection of the two lines. The two lines each become a linear inequality, e.g. "x+y >= 0", together forming the convex region the answer can be found in. I will note that the solution will be (x=x0, y=y0) - what you need from this stage a way of expressing the problem, analagous to a feasible tableau for the <a href="http://en.wikipedia.org/wiki/Simplex_algorithm" rel="nofollow noreferrer">simplex method</a>.</li> <li>Third, an integer solution can be found by repeatedly adding <a href="http://en.wikipedia.org/wiki/Cutting-plane_method#Convex_optimization" rel="nofollow noreferrer">cuts</a> to further constrain the feasible region until the solution to the convex optimization problem is integral. This stage may take a lot of iterations in the general case, but looking at the problem presented, and in particular the 2D nature of it, I believe it will be solved with at most two cuts.</li> </ol>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload