WTHINGS - Editorial

PROBLEM LINK:

Practice
Contest

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

4 Likes

My solution was also uses the exact same logic but it gives TLE. Here is my solution http://www.codechef.com/viewsolution/4130601. Can anyone tell me where I am getting TLE?

i had the same issue here. all i’ve done is changing iostream do cstdio (I was turning sync_with_stdio off, but had some issues in the past), and changed some unnecessary longs to 32 bit integers. Got AC with 5.37s using C++ (g++ 4.8.1)

1 Like

Can you explain a little bit better the binary/ternary search modifications you’ve made (like using min/max as the answer instead of the value of lo,hi)? What I know of binary and ternary search is the conventional usage, maybe I missed some tricks when using it on integers? I couldn’t understand that very well, and that’s what made my code fail in contest time ):

//