Need Help
There are N circles in a plane. Circle i and circle j form a good pair if it is possible to choose a point P1 on the perimeter of circle i and a point P2 on the perimeter of circle j such that the Euclidean distance between P1 and P2 is exactly K. (Note that P1 and P2 do not need to have integer coordinates.)
You should answer Q queries. In each query, you are given the required distance K. Chef is interested in finding the number of good pairs of distinct circles for each query. Please help him.
Note: Circle i and circle j are distinct when i≠j. There may be any number of circles that coincide (have identical centers and radii).
Input
The first line of the input contains two space-separated integers N and Q denoting the number of circles and the number of queries respectively.
Each of the following N lines contains three space-separated integers X, Y and R describing a circle with radius R and center (X,Y).
Each of the next Q lines contains one integer K describing a query.
Output
For each query, print a single line containing one integer — the number of good pairs of circles.
Constraints
2≤N≤103
1≤Q≤5⋅105
X,Y≤|2⋅105|
1≤R≤2⋅105
0≤K≤106
Example Input
2 3
0 0 5
8 3 2
0
10
20
Example Output
0
1
0
Explanation
The distance between the point (0.00,−5.00) on circle 1 and the point (8.00,1.00) on circle 2 is 10. There is no pair of points on these two circles with distance 0 or 20.
Can anyone help me in this question?I tried it but not able to get the right approach to it.I think that there might be some mathematical equation but not able to get that one .Can anyone guide me in this?
Thank you
You should answer Q queries. In each query, you are given the required distance K. Chef is interested in finding the number of good pairs of distinct circles for each query. Please help him.
Note: Circle i and circle j are distinct when i≠j. There may be any number of circles that coincide (have identical centers and radii).
Input
The first line of the input contains two space-separated integers N and Q denoting the number of circles and the number of queries respectively.
Each of the following N lines contains three space-separated integers X, Y and R describing a circle with radius R and center (X,Y).
Each of the next Q lines contains one integer K describing a query.
Output
For each query, print a single line containing one integer — the number of good pairs of circles.
Constraints
2≤N≤103
1≤Q≤5⋅105
X,Y≤|2⋅105|
1≤R≤2⋅105
0≤K≤106
Example Input
2 3
0 0 5
8 3 2
0
10
20
Example Output
0
1
0
Explanation
The distance between the point (0.00,−5.00) on circle 1 and the point (8.00,1.00) on circle 2 is 10. There is no pair of points on these two circles with distance 0 or 20.
Can anyone help me in this question?I tried it but not able to get the right approach to it.I think that there might be some mathematical equation but not able to get that one .Can anyone guide me in this?
Thank you
If you did try, then you have some code. Show it and then someone might point out where it wen't wrong.
If that is a "competitive programming" task, then nobody should help you, unless they get fair share of the fame too. Will they?
If that is a "competitive programming" task, then nobody should help you, unless they get fair share of the fame too. Will they?
If this is a Codechef problem, you should know that the Codechef adjudicators are aware of this forum, and that people use it to cheat on their contests. If you use this forum to try and cheat, you run the risk of being disqualified.
Topic archived. No new replies allowed.