~N~ lines.is learning how to calculate the intersections of lines in math class. Being quite good at math, he quickly becomes bored and fell asleep. In his dream, he descended into a 2-dimensional world containing
is wondering how many times the lines cross each other. Since there are way too many lines for to count, he calls you in desperation.
Each line is represented in slope-intercept form, where you are given both the slope and the y-intercept (~y=mx+b~).
Note that if there are multiple lines that cross each other at the exact same point, please count the pairs of lines that intersect at that point. More specifically, if ~N~ lines intersect at the same point, that point should be counted ~\binom N 2~ times.
If there are 2 lines that are congruent (with the same slope and y-intercept), print
Infinity (since 2 congruent lines intersect at infinite number of points).
Subtask 1 [90%]
~1 \le N \le 5000~
~-1000 \le m_i \le 1000~
~-1000 \le b_i \le 1000~
Subtask 2 [10%]
~1 \le N \le 10^5~
~-10^9 \le m_i \le 10^9~
~-10^9 \le b_i \le 10^9~
The first line contains an integer ~N~, indicating the number of lines you are given.
On each of the following ~N~ lines are 2 integers ~m_i~ and ~b_i~, indicating the slope and y-intercept of each of the lines.
On the first line output the number of pairs of lines that intersect.
Note: It is recommended to use 64-bit integers when computing the answer.
3 1 1 1 -1 -1 3
Explanation for Sample Output
The 3 lines intersect at ~(1,2)~ and ~(2,1)~.