SP11407 TDOWN - Tied Down

题目描述

众所周知,奶牛贝茜特别喜欢在农场上捣乱。为了管住她,农夫约翰决定用一根长绳子把贝茜固定在围栏上。从上往下看,围栏由 $N$ 根直立的柱子组成($1 \le N \le 10$)。贝茜的位置坐标是 $(bx, by)$,位于这条柱子垂直线的右侧。农夫用来捆住贝茜的绳子由 $M$ 条线段($3 \le M \le 10,000$)组成,绳子的起点和终点都是贝茜所在的位置。所有围栏柱子都不与这些线段相交。然而,线段之间可能会相互交叉,并且多条线段在端点处可能重合。 以下是此场景的一个示例图示: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/SP11407/d5fda3a4405def250111bf63ee1380fcd4cad90c.png) 为了帮助贝茜脱身,其他奶牛从谷仓里偷了一把锯子。请计算出她们必须锯断的最少的围栏柱子数量,以便贝茜能够顺利地向右逃跑(即,能够从围栏柱子间穿过,绳子不会被任何柱子缠住)。输入中所有的坐标值(包括围栏柱子、贝茜和线段端点的坐标)都在 $0 \ldots 10,000$ 范围内。所有的围栏柱子具有相同的 $x$ 坐标,并且 $bx$ 大于这个值。

输入格式

- 第一行:四个空格分隔的整数:$N, M, bx, by$。 - 接下来 $N$ 行:每行两个空格分隔的整数,表示第 $i$ 个围栏柱子的 $x$ 和 $y$ 坐标。 - 再接下来的 $M$ 行:每行两个空格分隔的整数,按顺序表示绳子上的一个点的 $x$ 和 $y$ 坐标。第一个和最后一个点均为贝茜的位置 $(bx, by)$。

输出格式

- 输出一行:需要移除多少根围栏柱子,才能让贝茜顺利逃脱。 **本翻译由 AI 自动生成**