CSU-ACM Online Judge

1272: Karma

      Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 172     Solved: 37    

Description

英雄联盟是一个第三人称竞技游戏,角色天启者-卡尔玛有一个技能是灵魂连接,可以在小兵和自己之间施放一道光束,如果光束(包括光束的两个端点)恰好扫到敌军的小兵,则会对其造成伤害。现在已知卡尔玛这个技能连接到了某个友军的小兵上,在技能持续的时间内,卡尔玛相继走到了若干个点,且在任意两个相邻点之间走的是直线,你能计算出一共有多少个敌军的小兵受到了伤害吗?假设卡尔玛和所有的小兵都可以视作质点,且在技能持续时间内所有的小兵都没有移动。

Input

输入数据第一行为一个整数T (1 <= T <= 200),表示接下来一共有T组测试数据。

对于每组测试数据,第一行包含两个整数N (1 <= N <= 1000), M (1 <= M <= 20)N表示敌军小兵的个数,M表示卡尔玛在技能持续时间内相继走到的点的数量。接下来一行包含四个整数,前两个整数描述了技能连接的友军小兵的坐标,后两个描述了卡尔玛刚施放技能时所在的坐标。接下来一共有N行,每行均包含两个整数,分别描述了敌军N个小兵的坐标。再接下来一共有M行,每行均包含两个整数,分别描述了卡尔玛相继走到的M个点的坐标。所有坐标均为绝对值不超过105的整数。

Output

对于每组测试数据,用一行输出一个整数,表示一共有多少个敌军的小兵受到了伤害。

Sample Input

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

Sample Output

1
2
1

Hint

Source

中南大学第七届大学生程序设计竞赛