19004번 - Rikka with Lines 다국어

Plane geometry is an important branch of elementary mathematics. When Rikka was a middle school student, she learned a lot of properties of lines, triangles, and circles.

As time went on, Rikka has learned various other branches of mathematics. Nowadays, she finds that the tasks about lines, triangles, and circles appear less and less. Rikka loves plane geometry because it is interesting and at the same time simple enough even for a middle school student. She misses such problems very much. 

So, Rikka wants to come up with some problems about lines for herself. She draws $n$ lines of the form $y = a_i x + b_i$ on the two-dimensional Cartesian plane. Then she selects a rectangle with the left bottom corner $(x_1, y_1)$ and the right top corner $(x_2, y_2)$. Rikka wants to count the number of pairs of lines $(i, j)$ ($i < j$) such that their intersection exists and lies inside the rectangle. Here, points on the rectangle border are also considered to lie inside.

It is a simple problem for Rikka, and she wants to test you. To show your mathematical skills, you need to solve this problem as fast as possible.

The first line contains a single integer $t$ ($1 \leq t \leq 10^3$), the number of test cases.

For each test case, the first line contains five integers $n$, $x_1$, $y_1$, $x_2$, and $y_2$ which satisfy $1 \leq n \leq 10^5$, $-10^{9} \leq x_1 < x_2 \leq 10^9$, and $-10^{18} \leq y_1 < y_2 \leq 10^{18}$.

Then $n$ lines follow. Each of these lines contains two integers $a_i$ and $b_i$ ($-10^9 \leq a_i \leq 10^9$, $a_i \neq 0$, $-10^{16} \leq b_i \leq 10^{16}$), describing a line.

It is guaranteed that no two given lines are actually the same line, and there are at most $5$ test cases with $n > 500$.

For each test case, output a single line with a single integer: the number of pairs of lines which intersect inside the given rectangle or on its border.