The first thing to notice is that, in order to obtain as many parts as possible, no three cuts will intersect in a common point. This is easy to see: if there is an intersection of three cuts, then we will get an extra part by moving slightly one of those cuts.

Now we can find a maximum number of parts as a function of number of used cuts:

$$\displaystyle number\_of\_parts(r) = 1 + \sum_{i=1}^r i$$

So we must find the minimum ~r~ for which ~number\_of\_parts(r) \ge K~. Since our function is obviously monotonic, we can use binary search to find the minimum ~r~.

If we output only the expected ~r~, we get ~50\%~ of the total number of points.

There are many ways to find the actual cuts, and here is the simplest one. Make the ~i^\text{th}~ cut by connecting these two points: ~(5000-i, -5000)~ and ~(-5000, -5000+i)~