FSHEEP - Fencing in the Sheep

no tags 

A shepherd is having some trouble penning in his flock of sheep. After several hours of ineffectual efforts he gives up, with some of the sheep within their polygon-shaped pen and some outside. Exhausted, he moves to a place within the pen from which he can see the whole interior of the pen (without any fence getting in the way) and begins to count the sheep which are within it. Please assist him in his task.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

The first line of each test case contains two integers n m, denoting the number of vertices of the polygon forming the fence, and the number of sheep in the whole herd (3<=n<=100000, 0<=m<=100000). The next n lines contain two integers each, the i-th being xi yi - the x and y coordinates of the i-th vertex of the fence (given in anti-clockwise order, -32000<=xi,yi<=32000). The next m lines contain two integers each, the j-th being xj yj - the x and y coordinates of the j-th sheep (arranged in decreasing order of seniority, -32000<=xj,yj<=32000). The shepherd's observation point is within the pen and has coordinates (0,0).

Output

For each test case output a line with a single integer - the number of sheep within the pen. The sheep which are sitting back on the fence and enjoying a cigarette should be included in the count.

Example

Sample input:
1
6 5
2 2
4 4
6 6
-3 1
-1 -1
5 1
2 1
3 2
6 6
3 3
-3 0

Sample output:
3

Illustration of the sample test data:

The sheep with their shepherd

Warning: large Input/Output data, be careful with certain languages

hide comments
paras meena: 2014-05-16 12:18:59

WA in C++4.3.2 AC in C++4.0.8 WTF!!!!.. :/

Tony Beta Lambda: 2009-08-17 06:47:39

What is seniority?
Miss Epsilon is key to success, though she is very small. 1e-8 is okay.

Last edit: 2009-08-18 03:36:52

Added by:adrian
Date:2004-07-24
Time limit:1.064s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002