Problem J

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.

\includegraphics[width=0.75\textwidth ]{bomas.png}

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\leq n,q \leq 10^5$), where $n$ is the number of existing bomas and $q$ is the number of queries.

Each of the next $n$ lines contains three space-separated integers $x$, $y$ ($-10^7 \leq x,y \leq 10^7$)
and $r$ ($1 \leq r \leq 10^7$), 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$ ($-10^7 \leq x,y \leq 10^7$)
and $r$ ($1 \leq r \leq 10^7$), 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 one another.


For each query output a line with a single integer, which is the number of animal types the zoo can display within the queried region.

Sample Explanation

\includegraphics[width=1.0\textwidth ]{bomassample.png}

This image illustrates the five queries of the sample Input/Output. The existing bomas are black, the query bomas are red, and the areas where animals can be placed are green. Note that for query $4$, putting animals only in the inner boma is also acceptable.

Sample Input 1 Sample Output 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
CPU Time limit 6 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in