PROBLEM LINK
Practice
Contest
Author and Editorialist: Souradeep Paul
Tester: Avijit Agarwal, Sarthak Manna
DIFFICULTY
Easy
PREREQUISTITES
Basic Math and Geometry, Binary Search
PROBLEM
There are N line segments and i'th segment connects points (a_i,0) and (0, a_i). You are also given Q queries and in each query given a point (x_i, y_i). For each query find the number of line segments present under this point and if the point already lies upon a line segment then print -1.
EXPLANATION
Equation of i'th line is x + y - a_i = 0, so for a point P(x_p, y_p) there are 3 possible scenarios,
- if x_p+y_p-a_i < 0, then P is under this line.
- if x_p+y_p-a_i = 0, then P is upon this line.
- if x_p+y_p-a_i > 0, then P is above this line.
So we can use binary search over the answer, let’s see how.
Now if you currently checking i'th segment and find that P is lying above the line then you have to break more line segment to allow Chef to reach (0, 0), so you can continue the searching upon upper half of the binary search. Otherwise, if P lie under the line then you are going to break more segments which is not possible as you can’t break segments which are above you, so you can continue the searching upon the lower half of the binary search. Lastly, if you find that P lies on a line in any step of binary search then you simply find that it’s not possible to reach (0, 0).
The time complexity is \mathcal{O}(Q\log{}N).
SOLUTIONS
C++ solution can be found here
Java solution can be found here
Python solution can be found here