Minimum Wire Crossings

Moore’s Law inspires us to pack more circuits onto chips. In two‐dimensional hardware design, routing wires can be problematic when they cross existing wires; every crossing increases manufacturing cost. Given several existing wires (each represented by a straight line segment) and two points representing the start and end of a new connection, your task is to determine the minimum number of wires you must cross in order to connect the two points. The connection may be arbitrarily curved, but it is not allowed to cross at a point where two or more wires already meet or intersect.

Input Format:
The input begins with an integer n representing the number of existing wires. Each of the next n lines contains 4 numbers: x1 y1 x2 y2, representing the endpoints of a wire. The final line contains 4 numbers: s_x s_y e_x e_y, which are the coordinates of the start and end points for the new connection.

Output Format:
Output a single integer: the minimum number of wires that must be crossed in order to connect the start and end points while obeying the restrictions.

Note: Crossing a wire means that the new connection and the wire intersect at a single point in the interior of the connection. A crossing at an endpoint is allowed only if that endpoint is incident to a single wire – if two or more wires meet at that point, you cannot cross there.

Mathematical formulation:
Assume the new connection is a continuous curve C joining the start point S and the end point T. For each given wire w (a line segment), let I_w = C \cap w be the set of intersection points. The cost of using connection C is defined as $$ \sum_{w}\mathbf{1}\Bigl[\exists p \in I_{w}\;\text{s.t.}\; p \;\text{is not an intersection point of two or more wires}\Bigr]. $$ The problem asks you to compute the minimum cost possible among all curves C joining S and T.

inputFormat

The first line contains an integer n (number of wires). The following n lines each contain 4 floating point numbers: x1 y1 x2 y2, which are the endpoints of a wire. The last line contains 4 floating point numbers: s_x s_y e_x e_y, specifying the start and end points.

Example:

8
0 0 0 1
0 1 1 1
1 1 1 0
1 0 0 0
2 0 2 1
2 1 3 1
3 1 3 0
3 0 2 0
0.5 0.5 2.5 0.5

outputFormat

Output a single integer – the minimum number of wires that must be crossed.

Example:

2

sample

8
0 0 0 1
0 1 1 1
1 1 1 0
1 0 0 0
2 0 2 1
2 1 3 1
3 1 3 0
3 0 2 0
0.5 0.5 2.5 0.5

2