Here is another idea.
Key observation:
Let $O$ be the origin in $\mathbb{R}^4$. Let $H$ be the convex hull of the set $\{O\} \cup \{l_i : 1 \leq i \leq n\}$. Then one may only consider those $l_i$ which are vertices of $H$. Same for those $r_j$.
Finding convex hulls can be done in $O(n \log n)$ time, c.f. wiki page.
The problem is then: how many vectors still remain after this procedure.
Under certain assumptions, e.g. the vectors are uniformly distributed, this reduction could be good enough to allow a brute force on the remaining vectors.