DMOPC '16 Contest 1 P2 - Lines

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 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).

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

Input Specification

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.

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

1 1
1 -1
-1 3

Sample Output


Explanation for Sample Output

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


  • 2
    odaniel  commented on Oct. 11, 2016, 5:13 p.m.

    In the graphic, shouldn't the line be -x+3?

    • 1
      jimgao  commented on Oct. 11, 2016, 5:43 p.m.

      Thank you for noticing. The graph has been corrected.

    • 4
      FatalEagle  commented on Oct. 11, 2016, 5:42 p.m. edited

      You're right. Note the general idea of the image remains the same, and only the label is wrong.

  • -4
    iNfaM0usBlue  commented on Oct. 11, 2016, 4:32 p.m.

    What does (N 2) mean...?

    • 3
      FatalEagle  commented on Oct. 11, 2016, 4:50 p.m.

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