Description

As we all know, Bessie the cow likes nothing more than causing mischief on the farm. To keep her from causing too much trouble, Farmer John ties Bessie to a fence with a long rope. Viewed from above, the fence consists of $N$ posts with $1 \le N \le 10$, arranged along a vertical line, with Bessie’s position $(b_x, b_y)$ located to the right of this vertical line. The rope that ties Bessie is described by a sequence of $M$ line segments with $3 \le M \le 10{,}000$, where the polyline starts and ends at Bessie’s position. No fence post lies on any rope segment. However, segments may cross, and multiple segments may overlap at their endpoints.

Here is an example of the scene, viewed from above:

To help Bessie escape, the other cows have stolen a saw. Determine the minimum number of fence posts they must cut and remove so that Bessie can pull free, meaning she can run to the right without the rope catching on any fence post.

All $(x, y)$ coordinates in the input (fence posts, Bessie, and rope endpoints) lie in the range $0 \ldots 10{,}000$. All fence posts share the same $x$ coordinate, and $b_x$ is larger than this value.

Input Format

• Line 1: Four space-separated integers: $N$, $M$, $b_x$, $b_y$.
• Lines $2 \ldots 1+N$: Line $i+1$ contains the space-separated $x$ and $y$ coordinates of fence post $i$.
• Lines $2+N \ldots 2+N+M$: Each of these $M+1$ lines gives, in order, the space-separated $x$ and $y$ coordinates of a point along the rope. The first and last points are both Bessie’s location $(b_x, b_y)$.

Output Format

• Line 1: The minimum number of posts that need to be removed for Bessie to escape by running to the right.

2 10 6 1 
2 3 
2 1 
6 1 
2 4 
1 1 
2 0 
3 1 
1 3 
5 4 
3 0 
0 1 
3 2 
6 1 
 

1 

Hint

There are two posts at (2, 3) and (2, 1). Bessie is at (6, 1). The rope goes from (6, 1) to (2, 4) to (1, 1), and so on, finally ending at (6, 1). The shape of the rope is the same as in the figure above.

Removing either post 1 or post 2 will allow Bessie to escape.

Translated by ChatGPT 5