Problem 106: Hants
(U.M. ACM Runoffs 2001, problem 6)
Description
The floor has been covered with hant poison, but the hants
have cleverly arranged for a bunch of sticks (of negligible
width) to be dropped on the ground in a jumble. A hant has
managed to get to one end of one of the sticks, and its
only source of food, a sugar lump, is also at one end of one
of the sticks. To survive, the hant must walk to the sugar
lump without ever touching the ground. The hant does not care
how far it walks, but for inviolable religious reasons he
must minimise the number of sticks that he walks along.
Given the positions of the fallen sticks, the hant, and the sugar
lump, find the minimum number of sticks that the hant must walk along.
Merely crossing over a stick that lies in his path does not
constitute walking along that stick.
It is guaranteed that the initial position of the hant and the
sugar lump will coincide with the position of the end of a stick.
The hant and the sugar lump will not start at the same positions.
Input Format
All positions are given as coordinates: a pair of integers, x first then y,
separated by a space.
The first line of the input file contains the starting position of the hant.
The second line contains the position of the sugar lump.
The third line contains a single integer, the number of sticks.
All subsequent lines contain the position of a fallen stick as four integers,
the position of one end followed by the position of the other end.
Output Format
The output should be a single line containing just a single integer, being
the minimum number of sticks that must be walked along, or zero if it is
not possible for the hant to reach the sugar lump.
Limits
No sticks will have zero length.
All coordinates will be integers >=0 and <1000000000.
There will not be more than 10000 sticks.
Sample Input
1 1
1 7
3
1 1 9 5
7 4 1 7
3 8 2 1
Sample Output
2
Explanatory Diagram
End of Problem