NC221286. Bomas
描述
You are a manager of a zoo. The zoo is a collection of enclosed areas formed by circular fences (known as bomas). The bomas do not intersect nor do they touch, but they can nest. You may choose not to use all of the zoo’s areas for holding animals at a given time (to prepare for future attractions). The animal types need to be separated by an empty enclosure, so for any two areas that share a border fence, at most one can hold animals (it might be the case that neither contain animals). Two different types of animals cannot be in the same area. Note that the “outer” area of the zoo can contain animals.
The zoo is looking to add a new boma. Given the existing bomas, how many animal types can the zoo display within the new boma subject to the above restrictions? The zoo has several options, so they will give you several queries, each consisting of a single boma to add. Only consider one query boma at a time; the queries are not cumulative.
输入描述
The first line of input contains two space-separated integers n and q (1 ≤ n, q ≤ 105), where n isthe number of existing bomas and q is the number of queries.Each of the next n lines contains three space-separated integers x, y (−107 ≤ x, y ≤ 107)and r (1 ≤ r ≤ 107), which describe an existing boma with center (x, y) and radius r.Each of the next m lines contains three space-separated integers x, y (−107 ≤ x, y ≤ 107)and r (1 ≤ r ≤ 107), which describe a query boma with center (x, y) and radius r.No two bomas of either type (existing or query) intersect or touch, but they can nest within oneanother.
输出描述
For each query output a line with a single integer, which is the number of animal types the zoo candisplay within the queried region.
示例1
输入:
3 5 0 0 100 0 50 20 0 -50 20 0 0 80 0 0 2 500 0 2 0 50 25 0 0 150
输出:
2 1 1 1 3