Let’s say I have n pairs of integers (not necessarily positive. The ith line consists of a pair of numbers ai and bi.

What is the quickest way to find if (bj - bi) / (ai - aj) lies within a certain range? I can only think of the usual O(N^2) solution but a solution of lesser time complexity?

I am trying to solve Anton and Lines from Round 329 on Codeforces.

Problem link: http://codeforces.com/contest/593/problem/B