A Walk in the Park
Time limit2sMemory limit128 MB
Given points for trees and infinite horizontal or vertical paths that avoid all trees, count trees visible along a perpendicular direction with no other tree blocking the sight line.
- Level
Medium6 of 10
- Topics
- Sorting, Hash map, Geometry, Implementation
- Solved
- No attempts yet
Problem
You are responsible for inspecting the trees in a park to keep them healthy. Each tree is a point in the two-dimensional plane, and no two trees share a location. Because of freshly replanted grass, you may only walk along a set of paths. Each path is an infinite horizontal or vertical line in the plane, and no tree lies on any path.
You are worried that some trees cannot be seen from the paths. A tree is visible only if, standing somewhere on a path and facing in a direction perpendicular to that path, you can see it with no other tree blocking your line of sight. (From a vertical path you look horizontally; from a horizontal path you look vertically.) Given the layout of the park, report how many trees are visible.
Input
The input contains several data sets. For each data set, the first line has two integers and () separated by a space: is the number of trees and is the number of paths.
The next lines each contain two space-separated integers and , the coordinates of a tree; and may be any 32-bit integers.
The next lines each describe one path — a vertical or horizontal line — in the form x=K or y=K with no spaces, where x and y are lower-case and may be any 32-bit integer.
The input ends with a line containing two space-separated zeros.
Output
For each data set, print a single line with one integer: the number of visible trees. Do not print any blank lines between outputs.