疯狂小镇是一个有n条无限直线道路的平面。每条道路由方程aix+biy+ci=0定义,其中ai和bi不都等于零。道路将平面划分为可能具有无限空间的连接区域。让我们把每个这样的区域称为一个块。我们将交叉点定义为至少两条不同道路相交的点。
你的家位于其中一个街区。今天你需要去大学,也在某个街区。在一个步骤中,如果块的公共边界长度为非零,则可以从一个块移动到另一个块(特别是,这意味着如果块与一个交点相邻,但没有共享的非零边界线段,则不允许在一个步骤中从一个移动到另另一个)。
确定到达包含大学的街区所需的最少步骤数。保证你的家和大学都不在路上。
1 1 -1 -1 2 0 1 0 1 0 0
2
1 1 -1 -1 3 1 0 0 0 1 0 1 1 -3
2
第一行包含两个空格分隔的整数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 2 0 1 0 1 0 0
2
1 1 -1 -1 3 1 0 0 0 1 0 1 1 -3
2
注意
样本图片如下(A是代表房子的点;B是代表大学的点,不同的块用不同的颜色填充):
1 1
-1 -1
2
0 1 0
1 0 0
2