Description

Translated from [CERC2018] Mirrority Report.

In physics class, each student must complete a midterm project. You choose to conduct an experiment to study the properties of a rare unstable particle called a red particle. A red particle always moves in a straight line until it is reflected by a mirror.

Our experiment can be viewed as a set of one-time mirrors. These mirrors can be considered as infinitely long straight lines in a 2D plane. A one-time mirror reflects the particle only the first time the particle reaches it. It can reflect the particle regardless of the incoming direction, but after that, the particle will just pass through the mirror.

During reflection, the law of reflection applies. If the particle reaches the intersection point of two mirrors, the particle will decay; otherwise, it will be reflected.

The arrangement of the mirrors is set by your lab instructor. Your task is to find how many starting directions from a given point will make the particle reach a specific point.

Input Format

The first line contains a non-negative integer $N$, the number of mirrors.

The second line contains four integers $S_x, S_y, E_x, E_y$, meaning the particle starts at $(S_x, S_y)$ and the destination is $(E_x, E_y)$.

The next $N$ lines each contain four integers $A_x, A_y, B_x, B_y$, representing two points on the $i$-th mirror.

All input coordinates are within $[-100, 100]$. The start point and the end point are different. The distance from the start point or the end point to any mirror is non-zero.

It is guaranteed that there is no valid configuration in which the distance between the incident point (where the particle hits a mirror that can reflect it) and the intersection point of two mirrors is less than $10^{-4}$.

Output Format

Output one integer in one line: the number of starting directions from $(S_x, S_y)$ that will make the particle reach $(E_x, E_y)$.

2
2 3 4 2
2 2 3 3
1 4 3 4

1

3
2 3 5 2
1 3 1 1
2 4 4 2
5 4 6 5

1

1
0 0 4 0
0 4 4 4

2

Hint

Sample 1 is shown in the figure below:

Sample 2 is shown in the figure below:

Sample 3 is shown in the figure below:

Constraints: $0 \le N \le 8$.

Translated by ChatGPT 5