Problem Code : BIT_PRAI
Problem Link : https://www.codechef.com/ONIG2019/problems/BIT_PRAI
Problem Setter : prnjl_rai (Pranjal Rai)
Explanation : First of all notice the nature of the given equations. Both of the equations denote a parabola.
(X−a1)^2=b1.Y+c1
(X−a1)^2=b1.Y+c1
and it is clearly mentioned that b1.b2<0 which implies that the given parabolas are opposite facing in nature. Now the problem asks for the minimum distance between these 2 parallel to Y axis i.e. the vertical distance.
So, first let us check whether these 2 parabolas touch or intersect each other? If yes, the minimum distance between them is 0. To do so, solve the given equations which will result in a quadratic equation
(b1-b2).X^2+2.(a1.b2-a2.b1).X+(b2.c1-b1.c2+b1.a2^2-b2.a1^2)=0
Check if the roots of obtained quadratic equation are real or imaginary. If the roots are real, given parabolas touch/intersect each other otherwise they don’t.
Now if the given parabolas don’t touch/intersect each other, we can apply ternary search to find the minimum distance between them as the distance function between them is bitonic in nature. According to the given constraints, the X co-ordinates of the vertices of the given parabolas will remain in range [-10^9,10^9]. Apply ternary search within the range(You can choose a bigger range to be on safe side). Inside the search operation check the vertical distance between 2 parabolas and shift the range of search accordingly.
Link to Setter’s Solution : Link