**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