title: Division of a convex hull into two separate parts
body: <p>I am trying to solve quite a difficult problem for me. I'm not new to programming, but I don't really know how to figure out this problem. It's given a set of points (point []) with Xi and Yi coordinates as an input. The program has to output circumference of a convex hull of the polygon, but if it is necessary, it can divide the hull into two parts, two separate convex hulls, for each will contain a number of points. The goal of this division is to have a shorter circumference (if a sum of circumference of those two hulls is shorter than circumference of one hull; for example: two clusters of points far away from each other). The problem also is that there can't be more than two hulls. I would appreciate any ideas.</p>
  
  <p>There's a simple illustration of that problem (there could be a lot more points). Here you can see that circumference of two separated hulls is shorter than circumference of one.
  <img src="https://i.stack.imgur.com/6gWE6.png" alt="enter image description here"></p>
  
  <p>ADD: Actually, by "circumference" I mean perimeter. </p>
  
  <p>Here's the key part of my code:</p>
  
  <pre><code>m.x = (a.x + b.x)/2;
      m.y = (a.y + b.y)/2;
  
      ab.first = b.x - a.x;
      ab.second = b.y - a.y;
  
      for (i=0; i&lt;n; ++i)
      {
          if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 &gt; 0)
              left[l++]=p[i];
          else if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 &lt; 0)
              right[r++]=p[i];
          if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 == 0)
              mid[md++]=p[i];
      }
  </code></pre>