2677. [Usaco2012 Open]tied
#2677. [Usaco2012 Open]tied
题目描述
众所周知，奶牛贝茜最爱的事情就是在农场恶作剧。为了避免她造成太多的麻烦，农夫约翰决定用一根长绳将贝茜
系在栅栏上。从上面俯瞰，围栏由N个x坐标相等的柱子(1<=N<=10)组成，贝茜的位置(bx,by)位于这些柱子组成的
直线的右侧。约翰用来约束贝茜的绳子由M条首尾相接的线段(3<=M<=10,000)构成，其中第一段从贝茜的位置开始
，最后一段在贝茜的位置结束。保证这些线段上没有栅栏柱；但是线段可能交叉，并且可能有多条线段在端点处重
叠。为了帮助贝茜逃跑，其他的牛从谷仓里偷了一把锯子。请确定为了让贝西能够自由拉动（即她可以在没有绳子
拴住任何栅栏柱的情况下跑到右边），他们必须锯断栅栏杆的最少数量。输入中的所有(x,y)坐标（栅栏柱子、贝
茜和线段端点的位置）位于0至10,000的范围内。所有栅栏柱子都具有相同的x坐标，并且bx大于此值。
输入格式
第一行四个整数N,M,bx,by。
接下来N行每行输入一根栅栏柱的坐标。
接下来M+1行按顺序输入绳子的端点坐标，保证第一个点和最后一个点与(bx,by)位置相同。
输出格式
输出一行一个整数：让贝茜走到右侧需要锯断的最少柱子数。
样例
样例输入
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
输入解释：有两个柱子(2,3)和(2,1)。贝茜在(6,1)。绳索从(6,1)到(2,4)到(1,1)，依此类推，最后终止于(6,1)。
样例输出
1
输出解释：锯断柱子1或柱子2可以使贝茜逃脱。