VMSS '15 #3 - Jeffrey and Roads

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 256M

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

Jeffrey bikes to school from his house every day. It's a great way to not pay the bus fee and get some exercise, but there is a problem: Jeffrey is scared of roads. Jeffrey has an innate fear of turn signals, stop signs, pavement, Goodyear tires, the colour green, and white paint. In order to minimise the amount of fear he experiences in his daily commute, find the least number of roads that Jeffrey must cross.

It is guaranteed that neither Jeffrey's house or Jeffrey's school is directly on top of a road. Jeffrey is not a hobo. (Edit: Are you sure? :) )

Input Specification

The first line of input will have four integers x_h, y_h, x_s, and y_s, giving the Cartesian coordinates of both Jeffrey's home and those of Jeffrey's school.

The next line will contain an integer n. Following are n lines in the form A B C. Each road will be represented by a line that is described by the equation Ax + By + C = 0 The line will extend on both ends to infinity.

It is guaranteed that -10^8 \leq x_h, y_h, x_s, y_s, A, B, C \leq 10^8. In addition, 0 \leq n \leq 10^3.

Output Specification

Print out the minimum number of roads that Jeffrey must cross when travelling from his house, (x_h, y_h) to his school, (x_s, y_s).

Sample Input

-2 -2 2 2
0 1 -1
1 0 -1
2 4 8
3 3 -16

Sample Output



  • 4
    bobhob314  commented on Sept. 23, 2015, 9:16 p.m. edit 4

    Heya all,

    In the sample, for the first two lines, wouldn't the equations simplify respectively to y=0 and x=0? In which case, wouldn't both lines intersect the origin (0,0)? Why is this not the case in the diagram?

    Thanks, Max

    Edit: Thanks Jeffrey. Love Max

    • 1
      JeffreyZ  commented on Sept. 23, 2015, 11:00 p.m.

      Yeah, sorry about that, you're completely right. It should be fixed now.