DMOPC '16 Contest 1 P2 - Lines

View as PDF

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

Authors:
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 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 ().

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 lines intersect at the same point, that point should be counted 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).

Input Specification

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

On each of the following lines are 2 integers and , 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

3
1 1
1 -1
-1 3

Sample Output

2

Explanation for Sample Output

The 3 lines intersect at and .

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

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

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

Thank you for noticing. The graph has been corrected.

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

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

What does (N 2) mean...?

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

It means "N choose 2", which is equal to