VMSS '15 #3 - Jeffrey and Roads

View as PDF

Submit solution


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

Authors:
Problem type

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 minimize 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 nor 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 \le x_h, y_h, x_s, y_s, A, B, C \le 10^8. In addition, 0 \le n \le 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
4
0 1 -1
1 0 -1
2 4 8
3 3 -16

Sample Output

3

Comments

There are no comments at the moment.