DMOPC '16 Contest 1 P2 - Lines - DMOJ: Modern Online Judge

DMOPC '16 Contest 1 P2 - Lines

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Problem type

jackyliao123 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 $N$ $N$ lines.

jackyliao123 is wondering how many times the lines cross each other. Since there are way too many lines for jackyliao123 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$ $y = m x + 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$ $N$ lines intersect at the same point, that point should be counted $\binom N 2$ $(\binom{N}{2})$ times.

If 2 lines are congruent (with the same slope and y-intercept), print Infinity (since 2 congruent lines intersect at an infinite number of points).

Constraints

Subtask 1 [90%]

$1 \le N \le 5000$ $1 \leq N \leq 5000$

$-1000 \le m_i \le 1000$ $- 1000 \leq m_{i} \leq 1000$

$-1000 \le b_i \le 1000$ $- 1000 \leq b_{i} \leq 1000$

Subtask 2 [10%]

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$

$-10^9 \le m_i \le 10^9$ $- 10^{9} \leq m_{i} \leq 10^{9}$

$-10^9 \le b_i \le 10^9$ $- 10^{9} \leq b_{i} \leq 10^{9}$

Input Specification

The first line contains an integer $N$ $N$ , indicating the number of lines you are given.

On each of the following $N$ $N$ lines are 2 integers $m_i$ $m_{i}$ and $b_i$ $b_{i}$ , indicating the slope and y-intercept of each of the lines.

Output Specification

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.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

$\text{[math]}$

The 3 lines intersect at $(1,2)$ $(1, 2)$ and $(2,1)$ $(2, 1)$ .

Comments

-4

iNfaM0usBlue commented on Oct. 11, 2016, 8:32 p.m.

What does (N 2) mean...?

3

FatalEagle commented on Oct. 11, 2016, 8:50 p.m.

It means "N choose 2", which is equal to $\frac{N \times (N - 1)}{2}$ $\frac{N \times (N - 1)}{2}$