title: Fair division of a kingdom
body: <p>Recently, I've attended programming competition. There was a problem from it that I am still mulling over.  Programming language does not matter, but I've wrote it in C++. The task was this:</p>
  
  <blockquote>
    <p>As you already know, Flatland is located on the plane. There are n
    cities in Flatland, i-th of these cities is located at the point <em>(xi,
    yi)</em>. There are <em>ai</em> citizens living in i-th city. The king of
    Flatland has decided to divide the kingdom between his two sons. He
    wants to build a wall in the form of infinite straight line; each of
    the parts will be ruled by one of the sons. The wall cannot pass
    through any city. To avoid envy between brothers, the populations of
    two parts must be as close as possible; formally, if <em>a</em> and <em>b</em> are
    the total number of citizens living in cities of the first and the
    second part respectively, the value of <em>|a - b|</em> must be minimized.
    Help the king to find the optimal division. Number of cities is less
    than 1000. And all coordinates are integers. Output of algorithm
    should be integer number of minimal <em>|a-b|</em></p>
  </blockquote>
  
  <p>Okay, if I knew the direction of line, it will be really easy task - binary search: <img src="https://i.stack.imgur.com/XeIwG.png" alt="Black numbers are population of cities, and red is total population in that part"></p>
  
  <p><strong>I don't want code</strong>, I want ideas because I don't have any. If I catch idea I can write code!</p>
  
  <p>I don't know optimal direction, but I think it could be found somehow. So could it be found or is this task solved other way?</p>
  
  <p>An example where the horizontal/vertical line is not optimal:</p>
  
  <pre><code>1
  
  \
   \
  2 \      1
  </code></pre>