PROBLEM LINK:
Author: Konstantin Sokol
Tester: Tasnim Imran Sunny
Editorialist: Praveen Dhinwa
DIFFICULTY:
MEDIUM HARD
PREREQUISITES:
binary search, convex polygons
PROBLEM:
You are given a strictly convex polygon. You are to process Q queries of the following type:
You are given two vertices B and C of the polygon and number S. You should output the number of vertices A, such that the area
of triangle ABC is greater than or equal to S. If the triangle ABC has area >= S, then we will call it a “good” triangle.
QUICK EXPLANATION
As area of triangle is base * height / 2. As base of the triangel is BC, B and C are fixed point, so length of BC is fixed.
Note that height of the triangle will vary with variation in point A. For a “good” triangle ABC, we can note that height of the
triangle should be atleast 2 * S / base.
First of all, we are looking for the point A, that makes the biggest area with B and C. For that purposes we can use the ternary search Then,
we consider all the points to the left of A and to the right of A separately, because now they form a monotonous function
(we have splited our initial convex function into two monotonous functions).
EXPLANATION
As area of triangle is base * height / 2. As base of the triangel is BC, B and C are fixed point, so length of BC is fixed.
Note that height of the triangle will vary with variation in point A. For a “good” triangle ABC, we can note that height of the
triangle should be atleast 2 * S / base.
Now as the base BC is fixed. We can notice that if we go anticlockwise or clockwise from B to C, perpendicular distance between the point A
and line BC will first increase then decrease. Let us call this function distance function. We can say that distance function
is convex or unimodal function.
Now we will iterate for points A from point B to C in anticlockwise and clockwise order. As the polygon is convex,
you can notice that perpendicular distance between A and line BC will first increase and then decrease. Hence the distance function is convex.
Please view the image.
We need to find points P, Q, R, S. Let us pick upper hull. First we will find the point X where
the distance function is maximum. eg. X = 2 is the point of maxima of distance function.
Finding the maxima or minima of convex function can easily be done by ternary search.
Now we will consider the points on the left of X and right of X separately. Observe that now distance function in individual parts
is a monotonic function. Finding a particular point in the monotonic function can be done by binary search.
eg. From (For both the parts from B to 2 and From 2 to C, distance function is convex).
We can find P by doing a binary search in the part from B to 2. Similarly Q can be found by doing a binary search in part 2 to C.
Note that we need to apply the same procedure for lower hull too.
Complexity
For each query, 2 ternary searches + 2 binary searches are being perfomed, So our overall time complexity over all the queries is O(Q * log (3/2) (N)). Note that log (3/2) (N) is the time complexity of ternary search.
where Q denotes number of queries and N denotes number of points of the polygon.