Determining position of point W.R.T to given line equation

Question

Problem from HackerRank::

Problem Statement:

There are \$N\$ lines. Each line has an index between \$1\$ and \$N\$. The slope of each line is negative, i.e. it goes from upper-left to lower-right.

There are \$Q\$ queries. Each of them is in the format \$L\$ \$R\$ \$x\$ \$y\$, and you should output whether there is any line with index between \$L\$ and \$R\$ and the point \$(x,y)\$ is under it. If there is, then the answer isYES, otherwiseNO`.

As you know, any line splits an infinite plane into two regions. The point \$(x,y)\$ is under the line if that point is at the same region with point \$(-\infty , -\infty)\$ . If the point lies on the line it does not count.

Input Format:

The first line contains \$N\$, the number of lines. The following \$N\$ lines each contains two integers \$m\$ and \$n\$ that describes the line \$mx + n = y\$.

Output Format:

For each query, output one line containing either YES or NO.

Sample Input:

2
-1 3
-2 -4
3
1 2 0 0
1 1 0 0
2 2 0 0

Sample Output:

YES YES NO

Explanation:

For this, I've submitted this code in Python, but in half of the test case, the time limit was exceeded.

n = int(input())
x = []
y = []
for i in range(n):
    l = list(map(int, input().split()))
    x.append(l[0])
    y.append(l[1])
q = int(input())

for i in range(q):
    p = list(map(int, input().split())) 
    L = p[0]-1
    R = p[1]-1
    X = p[2]
    Y = p[3]
    flag = 0
    for i in range(L,R+1,1):
        if(Y - x[i]*X - y[i] < 0):
            print("YES")
            flag = 1
            break;
    if(flag == 0):
        print("NO")

I can't understand how can I improve my code further. Because for loop to check from L to R is necessary. also the loop to execute every query is necessary. So in total 2 loops are needed. How can I reduce time here?

Answer 1

Note to potential future reviewers: This code appears to be suitable for Python 3 only.

Let's structure your code a little and see if we can fix the timing problem.

I propose the following order:

1. Global variables
2. Helper functions
3. Main function
   1. Input
   2. Actual calculations
4. if __name__ == '__main__':

The latter may not look familiar to you, but it's an include guard. It's a good practice to start using those, especially if you ever want to re-use parts of your code. Now your main only gets executed if the script is called directly, not when it's called by import.

Which leaves us after the first couple of edits with the following:

x = []
y = []


def ask_amount():
    return int(input())


def ask_lines(amount):
    for i in range(amount):
        l = list(map(int, input().split()))
        x.append(l[0])
        y.append(l[1])


def ask_queries(amount):
    return list(map(int, input().split()))


def main():
    ask_lines(ask_amount())
    q = ask_amount()
    for i in range(q):
        p = ask_queries(q)
        L = p[0]-1
        R = p[1]-1
        X = p[2]
        Y = p[3]
        flag = 0
        for i in range(L, R+1, 1):
            if(Y - x[i]*X - y[i] < 0):
                print("YES")
                flag = 1
                break
        if(flag == 0):
            print("NO")

if __name__ == '__main__':
    main()

Which still isn't much, but the structure is getting better. Note that I made your comma's breath ((L,R+1,1) is more readable when written as (L, R+1, 1) and there's no longer a ; behind your break. It's Python, we don't need semi-colons after break/continue etc.

One of the major things fixed now is your code was executing before you finished reading your input. That's usually a bad idea unless you're in some kind of do until told otherwise loop, which this wasn't. Now it waits for all input before it executes the rest.

I/O used to be:

2
-1 3
-2 -4
3
1 2 0 0
YES
1 1 0 0
YES
2 2 0 0
NO

Now it is:

2
-1 3
-2 -4
3
1 2 0 0
1 1 0 0
2 2 0 0
YES
YES
NO

There's still a couple of problems with it. We're now iterating an extra time, which can't be helpful for the time it takes to execute. But at least it looks better now, so we can see what we're doing. It still fails just as many test cases as your original code did, so at least we didn't do noticeably worse.

What else can we do better?

    L = query[0]-1
    R = query[1]-1
    X = query[2]
    Y = query[3]
    flag = 0
    for i in range(L, R+1, 1):

R = some value minus one. The actual value we need is R plus one. Since the description of the challenge says L and R are given (not L+1 and R+1), it doesn't make sense to modify them.

Let's go from L-1 to R instead.

    L = query[0]
    R = query[1]
    X = query[2]
    Y = query[3]
    flag = 0
    for i in range(L-1, R, 1):

Another thing we don't need is this entire flag business. Let's use return values instead:

x = []
y = []


def ask_amount():
    return int(input())


def ask_lines(amount):
    for i in range(amount):
        l = list(map(int, input().split()))
        x.append(l[0])
        y.append(l[1])


def ask_queries(amount):
    return list(map(int, input().split()))


def does_line_exist(query):
    L = query[0]
    R = query[1]
    X = query[2]
    Y = query[3]
    for i in range(L-1, R, 1):
        if(Y - x[i]*X - y[i] < 0):
            return True
    return False


def main():
    ask_lines(ask_amount())
    q = ask_amount()
    queries = []
    for i in range(q):
        queries.append(ask_queries(q))
    for query in queries:
        if does_line_exist(query):
            print("YES")
        else:
            print("NO")

if __name__ == '__main__':
    main()

Poof! No more flag.

But wait, this still doesn't solve your TLE problem! No, I'm afraid not and I'm going to tell you why. The author of the problem has made the constraints so narrow that the only acceptable solutions are those which use the Convex hull trick. It basically boils down to checking whether a value is < -y instead of < 0.

I'll leave the actual implementation of said trick to you. Feel free to post a follow-up question once you've implemented it.