Description

On a 2D plane, there is a mirror channel formed by mirrors $AC$ and $BD$. The lengths of $AC$ and $BD$ are equal, and both are parallel to the $x$-axis. $B$ is at (0, 0).

Inside the channel, there are $n$ optical elements whose outer surfaces are mirrors. Element $\alpha$ is a circle, and element $\beta$ is a rectangle (these elements may intersect with other elements and with the channel; see the figures). A light ray can enter the channel from any point on $AB$ at any angle, and the light ray does not attenuate. If an element just touches another element, or an element just touches the channel boundary, the light is considered unable to pass through at that contact (for example, two tangent circles).

All information about the elements in the channel is given ($\alpha$ elements include the center coordinates and radius $x_i, y_i, r_i$; $\beta$ elements include the lower-left and upper-right corner coordinates $x_1, y_1, x_2, y_2$).

As shown in the first figure, $S$ to $T$ is a valid path.

Of course, there are cases where the light cannot pass through. Your task is to find the minimum number of optical elements that must be removed so that there exists a light path that can exit from $CD$.

An example is shown below: if the middle rectangle is removed, a light path passing through the channel can be constructed, as shown by $S$ to $T$.

Input Format

• The first line contains two integers, $x, y$, denoting the coordinates of point $C$.
• The second line contains an integer $n$, the number of optical elements.
• Each of the next $n$ lines begins with a number. If it is $1$, it denotes an $\alpha$ element, followed by three integers $x_i, y_i, r_i$ for the circle’s center and radius. If it is $2$, it denotes a $\beta$ element, followed by four integers $x_1, y_1, x_2, y_2$ for the rectangle’s lower-left and upper-right corner coordinates (rectangles are axis-aligned).

Output Format

Output one line containing a single integer $m$, the minimum number of optical elements that need to be removed.

1000 100
6
1 500 0 50
2 10 10 20 100
2 100 10 200 100
2 300 10 400 100
2 500 10 600 100
2 700 0 800 100

2

Hint

Constraints: $x \leq 10^5$, $y \leq 1000$, $n \leq 300$.

Translated by ChatGPT 5