Minimum Optical Element Removal for Light Passage

In a two‐dimensional plane there is a mirror channel bounded by two fixed mirror segments, \(AC\) and \(BD\), which are of equal length and parallel to the \(x\)‑axis; point \(B\) is at \((0,0)\). The channel contains \(n\) optical elements whose outer surfaces are mirrors. There are two types of optical elements:

• Type \(\alpha\): circles, given by center coordinates \((x_i,y_i)\) and radius \(r_i\).
• Type \(\beta\): axis‐aligned rectangles, given by the bottom‐left corner \((x_1,y_1)\) and the top‐right corner \((x_2,y_2)\).

A light ray can be injected into the channel from any point on side \(AB\) (the entry boundary) at an arbitrary angle, and its intensity does not decrease. However, if two optical elements or an element and the channel boundary are exactly touching (i.e. they are tangent), the ray is considered blocked at that contact.

The mirrors that form the channel (which we do not remove) are fixed along the lines \(y=0\) (corresponding to mirror \(BD\)) and \(y=1000\) (corresponding to mirror \(AC\)); these play the role of the "floor" and "ceiling" of the channel respectively. An optical element is said to touch the bottom boundary if, for an \(\alpha\)-element, \(y_i - r_i \le 0\) (or for a \(\beta\)-element, if \(y_1 \le 0\)); similarly, it touches the top boundary if, for an \(\alpha\)-element, \(y_i + r_i \ge 1000\) (or for a \(\beta\)-element, if \(y_2 \ge 1000\)).

The obstacles (optical elements) may overlap or even intersect the channel boundaries. They block any light path if they form a continuous chain connecting the top and bottom boundaries (in other words, if there exists a sequence of elements such that each two consecutive elements are touching and one element touches the top boundary and another touches the bottom boundary, then no light ray from the entry to the exit can pass through).

Your task is to determine the minimum number of optical elements to remove so that there exists at least one valid light path from the entry boundary \(AB\) to the exit boundary \(CD\). Note that when an element is removed it no longer contributes to the blockage chain. A valid light path exists if and only if, after removals, there is no connected chain (using the "touching" relation described below) between the top and bottom boundaries.

Touching condition between two optical elements:

• Circle - Circle: They are touching if the distance between their centers \(\le r_1+r_2\).
• Rectangle - Rectangle: They are touching if their projections on both the \(x\)-axis and \(y\)-axis overlap (adjacent or intersecting, i.e. touching is allowed).
• Circle - Rectangle: They are touching if the distance from the circle center to the rectangle is \(\le\) the circle's radius. (Formally, if \(dx = \max(\text{rect.x1}-x,0,x-\text{rect.x2})\) and \(dy = \max(\text{rect.y1}-y,0,y-\text{rect.y2})\), then they are touching if \(dx^2+dy^2 \le r^2\)).

Input note: The channel’s floor is \(y=0\) and ceiling is \(y=1000\). The optical elements are given in the input with their type followed by their parameters.

inputFormat

The first line contains an integer \(n\) (\(0 \le n \le 15\)), the number of optical elements. Each of the next \(n\) lines describes an optical element.

Each optical element is given in one of the following formats:

• For a circle (type \(\alpha\)): alpha x y r where \(x, y, r\) are floating‑point numbers.
• For a rectangle (type \(\beta\)): beta x1 y1 x2 y2 where \(x1, y1, x2, y2\) are floating‑point numbers and \(x1 < x2, y1 < y2\).

The channel boundaries are fixed at \(y=0\) (bottom) and \(y=1000\) (top).

outputFormat

Output a single integer — the minimum number of optical elements that must be removed so that there exists a valid light path from side \(AB\) (entry) to side \(CD\) (exit), i.e. so that no connected chain of remaining elements touches both the top and bottom boundaries.

sample

0

0

</p>