Domino Killing

One of the games I played most as a child is dominoes. Not the original game where tiles are laid flat and the numbers are matched up, but the one where the tiles stand upright in a long chain, the first tile is pushed, and the rest topple.

When the tiles are placed badly, not all of them fall. Given the layout and the direction of the first push, work out how many dominoes topple.

The dominoes stand on a board at integer coordinates. The $x$ axis runs from left to right and the $y$ axis runs from top to bottom. Seen from above, a domino is a short line segment, and its orientation is one of |, -, /, \.

The black lines are the tops of the dominoes and the red marks show where each one lands if it is pushed. A domino falls in one of the two directions perpendicular to its own segment and lands on exactly one neighbouring cell. A domino standing at $(x, y)$ lands as follows.

• |: $(x-1, y)$ or $(x+1, y)$
• -: $(x, y-1)$ or $(x, y+1)$
• /: $(x-1, y-1)$ or $(x+1, y+1)$
• \: $(x+1, y-1)$ or $(x-1, y+1)$

The dominoes are sized so that a falling one pushes only the domino standing on the cell it lands on. The pushed domino falls in whichever of its own two directions has a positive dot product with the incoming direction.

If a falling domino hits a domino at 90 degrees to it, that second domino does not topple. The one that hit it still counts as toppled. The pairs at 90 degrees are | with -, and / with \. For two dominoes that are not at 90 degrees the dot product is never zero, so the direction of the fall is fixed.

Pushing a domino that has already fallen does nothing.

The name of this problem comes from the way a translation tool rendered ドミノ倒し, the Japanese name of this game.

The input holds several test cases. The first line of each case has four integers separated by spaces: the number of dominoes $N$ ($1 \le N \le 100000$), the index $S$ of the domino that is pushed first ($0 \le S < N$, with the dominoes numbered from 0 in the order they appear in the input), and the push direction $F_x$ and $F_y$, where $F_x$ and $F_y$ are each -1, 0, or 1.

Each of the next $N$ lines describes one domino with two integers and one symbol separated by spaces. The integers are the coordinates $x$ and $y$ ($0 \le x, y \le 100000$), and the symbol is the orientation seen from above, one of |, -, /, \. No two dominoes stand on the same cell.

$(F_x, F_y)$ is always one of the two directions in which domino $S$ can fall. For example, if the orientation of domino $S$ is |, then $(F_x, F_y)$ is $(1, 0)$ or $(-1, 0)$.

The last line has four zeros. It is not a case and must not be processed.

For each case, print on one line the number of dominoes that topple. The domino that was pushed first is included in the count.

In the first case the top domino is pushed in direction $(0, 1)$, which is downwards in the diagram. It topples the next one, that one topples the next, and all four fall.

In the second case the domino at $(0, 1)$ is pushed in direction $(0, 1)$. It topples the domino at $(0, 2)$, which topples the domino at $(1, 3)$, and so on until all eight are down. When the domino at $(1, 0)$ falls, nothing further happens because the domino at $(0, 1)$ is already lying down.

In the third case the domino at $(1, 0)$ is pushed to the right. Only the dominoes at $(2, 0)$ and $(3, 1)$ topple. The domino at $(4, 2)$ is pushed by the domino at $(3, 1)$ but does not fall, because it stands at 90 degrees to it.