I'm facing the following problem: I'm given a set of coordinates on an integer grid that define the vertices of a polygon. The polygon is guaranteed to be convex. It's proven that such a polygon can always be cut into 4 equal area parts by 2 orthogonal lines. Let's call the point of these lines' intersection P.
Given that set, I should calculate the coordinates of P within the polygon and the angle the lines need to be turned on so that the lines cut the polygon into 4 equal parts.
I realise that, put generally, the cake cutting problem has no "good" solution. But this particular case of it should. I've searched for an algorithm to solve that problem, but found nothing useful. Where should I look?
My approach would be to calculate the coordinates of the centre of the polygon (that can be done more or less easily), place Pthere and then "wiggle" the lines until the areas of the parts match. But that sounds too inelegant.
UPD: that question is about a similar problem, but mine differs from it by the input I'm given. Further Update: since the vertices of the polygon belong to an integer grid, its' area can be found with Pick's formula, which might simplify the task a bit.
For each direction $\theta$, there is a unique (since $P$ is convex) line along that direction that bisects the polygon. Given a direction, you can find the lines along that direction and perpendicular to that direction that bisect the polygon, and then look at the area in the first quadrant (relative to those two lines) minus the area in the second quadrant. This signed area (call it $f(\theta)$) changes continuously from some value $f(0)=x$ when the direction is $\theta=0$ to the equal and opposite value $f(\pi/2)=-x$ when the direction is $\theta=\pi/2$; when the signed area is zero, the polygon is cut into four equal pieces. Clearly (by the intermediate value theorem) there is a point where the value is zero in the interval $\theta\in[0,\pi/2]$, and it can be found by a simple bisection search over $\theta$.