Time Limit: 18000/9000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

General Zhang recently got a plasma shield to intercept incoming missiles.

The shape of the plasma shield is basically a square with a horizontal diagonal. Due to some technology issues, the plasma shield cannot protect the whole square area. One vertical stripe in the middle of the square is penetrable to the missiles. So, in fact the shield is formed by two identical isosceles right triangle. Missiles hitting the surface or the edge of the shield are considered intercepted.

Now $N$ missiles are coming to General Zhang’s army. The $i-th$ missile will strike the position $(x_i,y_i)$. Because he only has one plasma shield, he want to calculate when the shield is turned on in a particular way, how many of the missiles it can stop.

General Zhang will give you $M$ queries, each query describe the shape of a plasma by 4 integers $(X,Y,D,W)$. $(X,Y)$ denotes the center of the shield. $D$ denotes the length of the diagonal. $W$ denotes the width of the unprotected stripe. For each query, you need to output number of the missiles stopped by the shield.

The shape of the plasma shield is basically a square with a horizontal diagonal. Due to some technology issues, the plasma shield cannot protect the whole square area. One vertical stripe in the middle of the square is penetrable to the missiles. So, in fact the shield is formed by two identical isosceles right triangle. Missiles hitting the surface or the edge of the shield are considered intercepted.

Now $N$ missiles are coming to General Zhang’s army. The $i-th$ missile will strike the position $(x_i,y_i)$. Because he only has one plasma shield, he want to calculate when the shield is turned on in a particular way, how many of the missiles it can stop.

General Zhang will give you $M$ queries, each query describe the shape of a plasma by 4 integers $(X,Y,D,W)$. $(X,Y)$ denotes the center of the shield. $D$ denotes the length of the diagonal. $W$ denotes the width of the unprotected stripe. For each query, you need to output number of the missiles stopped by the shield.

The first line of input contains an integer $T$ ($T≤20$), which represents the number of test cases.

Each test case starts with $N$ and $M$ ($1≤N,M≤20000$) in a line. The $i-th$ line of the next $N$ lines contains two integers $x_i$ and $y_i$. The next $M$ lines each line has 4 integers $X,Y,D,W$, which represents a query. $D$ and $W$ are guaranteed to be even numbers.

Each test case starts with $N$ and $M$ ($1≤N,M≤20000$) in a line. The $i-th$ line of the next $N$ lines contains two integers $x_i$ and $y_i$. The next $M$ lines each line has 4 integers $X,Y,D,W$, which represents a query. $D$ and $W$ are guaranteed to be even numbers.

提交代码