There are two non-intersecting convex polygon strictly inside a circle. The problem is to draw a line such that the polygons are on the different side of the line , the area of the part containing the first polygon is minimum. The inputs are such that you can always draw such a line. How to solve this problem ? number of points <= 50000
Problem name: circular island Problem link : https://codeforces.com/gym/101370/attachments/download/5499/20092010-summer-petrozavodsk-camp-petr-mitrichev-contest-5-en.pdf
Consider two outer tangents (left drawing below). Otherwise, the line must past through one of vertices of the first (blue) polygon. When we rotate the line in one of two directions, the area will become smaller — unless we are in the local minimum (of the function from angle to area). This possibility is shown on the right picture — when the line is perpendicular to the radius going through the fixed vertex. It's either this or it's optimal to rotate the line in one direction, so we would stop when we reach a segment.
So we should consider: two outer tangents, a line containing a segment of the blue polygon, or going through a vertex and perpendicular to the radius. This gives us O(n) candidates. For each we can check the area in O(1) and in O(log) we can check if it intersects the red polygon. Maybe we can avoid the "log" if we use the fact that lines aren't random — we can get them sorted by the direction.
Thank you , Errichto. But how do you test whether a line intersects a convex polygon in O(logn) ??
Split the convex hull into upper and lower half. For each half, binary search the intersection. Inside the binary search, for a vertex we should say in which direction (clockwise or counter-clockwise) we should go to be closer to the line.