CIRCP - Circle Counting

no tags 

In this problem, you will be given N circles, and M points. You are required to find out that inside how many circles does each of the M points lie. None of the M points will lie on any of the N circle boundaries (they will either lie inside a circle or outside it, but not on the circle).

Input

 

The 1st line gives the number of test cases T.
Each of the next T test cases has a format as explained below.
The 1st line of each test case contains 2 integers N and M.
Each of next N lines contains 3 integers cx, cy, r. The circle is located at center (cx, cy) and has a radius r.
Each of the following M lines contain 2 integers (x, y), which indicate that the location of the point.

 

 

The 1st line gives the number of test cases T.

Each of the next T test cases has a format as explained below.

The 1st line of each test case contains 2 integers N and M.

Each of next N lines contains 3 integers cx, cy, r. The circle is located at center (cx, cy) and has a radius r.

Each of the following M lines contain 2 integers (x, y), which indicate that the location of the point.

 

 

 

Output

 

For each of test case, print M lines, each correspoding to the no of circles inside which the corresponding point lies.

Separate each test case with a blank line.

 

Example

Input:
1
2 3
3 3 2
1 1 2
1 1
2 2
3 3

Output:
1
2
1
Sample diagram
Constraints
T <= 100
0 <= N <= 500
0 <= M <= 500
-1000 <= cx <= 1000
-1000 <= cy <= 1000
-1000 <= x <= 1000
-1000 <= y <= 1000
1 <= r <= 1000

hide comments
Sergio Dario Reyes Galvis: 2010-12-05 00:20:01

This exercise seems to apply a big set of test cases. so be careful with the functions you use here, this program HAS to be FAST.

Sergio Dario Reyes Galvis: 2010-12-05 00:03:41

Pratik,

Please extend the input and output example to show how it looks when you're using more than 1 test case.


Added by:.:: Pratik ::.
Date:2010-04-17
Time limit:2.530s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET