C - Crazy Town

Problem description

Crazy Town is a plane on which there areninfinite line roads. Each road is defined by the equationa_ix + b_iy + c_i = 0, wherea_iandb_iare not both equal to the zero. The roads divide the plane into connected regions, possibly of infinite space. Let's call each such region a block. We define an intersection as the point where at least two different roads intersect.

Your home is located in one of the blocks. Today you need to get to the University, also located in some block. In one step you can move from one block to another, if the length of their common border is nonzero (in particular, this means that if the blocks are adjacent to one intersection, but have no shared nonzero boundary segment, then it are not allowed to move from one to another one in one step).

Determine what is the minimum number of steps you have to perform to get to the block containing the university. It is guaranteed that neither your home nor the university is located on the road.

Input

The first line contains two space-separated integersx₁,y₁( - 10⁶ ≤ x₁, y₁ ≤ 10⁶) — the coordinates of your home.

The second line contains two integers separated by a spacex₂,y₂( - 10⁶ ≤ x₂, y₂ ≤ 10⁶) — the coordinates of the university you are studying at.

The third line contains an integern(1 ≤ n ≤ 300) — the number of roads in the city. The followingnlines contain 3 space-separated integers ( - 10⁶ ≤ a_i, b_i, c_i ≤ 10⁶;|a_i| + |b_i| > 0) — the coefficients of the linea_ix + b_iy + c_i = 0, defining thei-th road. It is guaranteed that no two roads are the same. In addition, neither your home nor the university lie on the road (i.e. they do not belong to any one of the lines).

Output

Output the answer to the problem.

Examples

Input

Output

Input

Output

Note

Pictures to the samples are presented below (A is the point representing the house; B is the point representing the university, different blocks are filled with different colors):

解题思路：题目的意思就是有n条直线（它们互不重合且其方程满足ax+by+c=0）把一个平面分成很多块，家和学校这两个坐标点必在其中一个块中，规定从一个块到与之相邻的另一个块所走步数为1（不能走没有相邻的块），求从家到学校走的最小步数。分析一下走法可知，从家到学校路途中，跨过相邻的块必经过一条直线，且这条直线在A、B两点之间，因此可以得出最小步数为A、B两点之间直线的条数。怎么判断条数呢？回想一下，高中学过的线性规划，在判断可行域的时候，通常以某个点例如（0，0）来判断可行域属于直线上方还是下方，上方为正，下方为负。因此这道题刚好就运用到这一知识点：把A(x1,y1)，B(x2,y2)分别代到n个方程中，只要每个方程的两个结果满足一正一负（直线的两侧），就将步数加1，最后即为最小步数。注意本题判断方法中的相乘可能导致数据溢出，因此将所有数据类型定义为long long，避免出错。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 int main(){
 5     LL x1,y1,x2,y2,n,a,b,c,step=0;
 6     cin>>x1>>y1>>x2>>y2>>n;
 7     while(n--){
 8         cin>>a>>b>>c;
 9         if((a*x1+b*y1+c>0)&&(a*x2+b*y2+c<0))step++;
10         if((a*x1+b*y1+c<0)&&(a*x2+b*y2+c>0))step++;
11     }
12     cout<<step<<endl;
13     return 0;
14 }

优质内容筛选与推荐>>
1、第二章、Django以及数据库的配置
2、css样式重置
3、[zz] Python 3.7 anaconda environment - import _ssl DLL load fail error
4、Asp.Net Core 发布和部署（ MacOS + Linux + Nginx ）
5、使用java实现输出101到200之间共多少个素数问题，并在优化的基础上打印所有

0 │ 收藏 │ 举报

Problem description

Input

Output

Input

Output

Input

Output

朋友将在看一看看到

分享想法到看一看