Question 9 - Polygonal Lines
- Problem Sheet
- This problem is not necessarily as hard as the question sheet might suggest, but it is one of those questions for which the solution is finicky. This trick is realising that in order to 'slide' the two pieces away along a certain line, every other cut must, for at least one 'side' of the line, be either all to the 'left' of the line or all to the 'right' of that line. In other words, if you place all of the cuts in a circle based on their angle, if more than half the circle is used there is no solution, otherwise whichever of the two 'outer-most' angles came first is the solution. In practice we solve this by only tracking the two 'boundary' angles right from the start, one of which is only allowed to move clock-wise and the other anti-clockwise. This is one of the relatively heavy 'maths' questions where you needed to understand how concave and convex verticies interact with the shape formed on either side of the line. The trickiest part is dealing with the angles that cross-over the 360/0 degree mark, and making sure that a 180 degree line doesn't 'activate' both the clockwise and the anti-clockwise boundary markers.
- Sample Solution [input=>output]