8368: Tied Down
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：0
题目描述
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 decides to tie Bessie down to a fence with a long rope. When viewed from above, the fence consists of N posts (1 <= N <= 10) that are arranged along vertical line, with Bessie's position (bx, by) located to the right of this vertical line. The rope FJ uses to tie down Bessie is described by a sequence of M line segments (3 <= M <= 10,000), where the first segment starts at Bessie's position and the last ends at Bessie's position. No fence post lies on any of these line segments. However, line segments may cross, and multiple line segments may overlap at their endpoints. Here is an example of the scene, viewed from above:
To help Bessie escape, the rest of the cows have stolen a saw from the barn. Please determine the minimum number of fence posts they must cut through and remove in order for Bessie to be able to pull free (meaning she can run away to the right without the rope catching on any of the fence posts). All (x,y) coordinates in the input (fence posts, Bessie, and line segment endpoints) lie in the range 0..10,000. All fence posts have the same x coordinate, and bx is larger than this value.
To help Bessie escape, the rest of the cows have stolen a saw from the barn. Please determine the minimum number of fence posts they must cut through and remove in order for Bessie to be able to pull free (meaning she can run away to the right without the rope catching on any of the fence posts). All (x,y) coordinates in the input (fence posts, Bessie, and line segment endpoints) lie in the range 0..10,000. All fence posts have the same x coordinate, and bx is larger than this value.
输入格式
* Line 1: Four space-separated integers: N, M, bx, by.
* Lines 2..1+N: Line i+1 contains the space-separated x and y coordinates of fence post i.
* Lines 2+N..2+N+M: Each of these M+1 lines contains, in sequence, the space-separated x and y coordinates of a point along the rope. The first and last points are always the same as Bessie's location (bx, by).
* Lines 2..1+N: Line i+1 contains the space-separated x and y coordinates of fence post i.
* Lines 2+N..2+N+M: Each of these M+1 lines contains, in sequence, the space-separated x and y coordinates of a point along the rope. The first and last points are always the same as Bessie's location (bx, by).
输出格式
* Line 1: The minimum number of posts that need to be removed in order 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