← 返回题目列表

Codeforces · 498/A

A. 疯狂小镇

中文机器翻译题面 查看原题

疯狂小镇是一个平面,上面有n条无限线道路。每条道路均由方程 aix + biy + ci = 0 定义,其中 ai 和 bi 不都等于零。道路将位面划分为相互连接的区域,可能具有无限的空间。我们将每个这样的区域称为一个块。我们将交叉口定义为至少两条不同道路相交的点。

您的家位于其中一个街区。今天您需要前往大学,该大学也位于某个街区。在一个步骤中,如果它们的公共边界的长度不为零,则可以从一个块移动到另一个块(特别是,这意味着如果块与一个交叉点相邻,但没有共享的非零边界段,则不允许在一步中从一个块移动到另一个块)。

确定到达包含大学的街区所需执行的最少步骤数是多少。可以保证您的家和大学都不在路上。

输入

第一行包含两个空格分隔的整数 x1, y1 (- 106 ≤ x1, y1 ≤ 106) — 您家的坐标。

第二行包含两个由空格分隔的整数 x2, y2 (- 106 ≤ x2, y2 ≤ 106) — 您正在就读的大学的坐标。

第三行包含一个整数n (1 ≤ n ≤ 300) — 城市中的道路数量。以下 n 行包含 3 个空格分隔的整数 (- 106 ≤ ai, bi, ci ≤ 106; |ai| + |bi| > 0) — aix + biy + ci = 0 行的系数,定义第 i 条路。保证没有两条路是相同的。此外,您的家和大学都不在路上(即它们不属于任何一条线路)。

输出

输出问题的答案。

示例

输入 #1

1 1
-1 -1
2
0 1 0
1 0 0

输出 #1

2

输入 #2

1 1
-1 -1
3
1 0 0
0 1 0
1 1 -3

输出 #2

2

注意

样本图片如下(A为代表房屋的点;B为代表大学的点,不同的块填充不同的颜色):