Cow Optics

Time limit1sMemory limit128 MB

Summary

Count empty integer points where one added 45-degree mirror steers the northbound laser from the origin to the barn through the existing mirrors.

Level: Medium6 of 10
Topics: Simulation, Sorting, Geometry
Solved: No attempts yet

Problem

A laser at $(0,0)$ points north toward a barn at $(B_x, B_y)$ . $N$ cows already hold 45-degree mirrors ( $\backslash$ or $/$ ) at distinct integer points. Bessie may place one more mirror at an empty integer point (not $(0,0)$ and not an existing cow) so the laser reaches the barn. Count valid locations. Mirrors reflect axis-aligned beams: $\backslash$ maps north to west, west to north, south to east, east to south; $/$ maps north to east, east to south, south to west, west to north.

Input

Line 1: $N$ , $B_x$ , $B_y$ . Next $N$ lines: mirror $x$ , $y$ , orientation ( $\backslash$ or $/$ ). Coordinates are integers in $[-10^9, 10^9]$ .

Output

One integer: the number of valid placement locations.

Examples3

Example 1
Input
```
4 1 2
-2 1 \
2 1 /
2 2 \
-2 2 /
```
Expected output
```
2
```
Example 2
Input
```
0 3 3
```
Expected output
```
1
```
Example 3
Input
```
1 5 0
5 5 \
```
Expected output
```
1
```