Black Discs

All submissions for this problem are available.
Consider the 2d plane which is white. You are given n semidiscs on it which are colored black. They are placed on the x  axis at various positions, in such a way that its center is on the xaxis and the entire semidisc is on or above the xaxis. By center of a semidisc, we mean the center of the disc of which it is a part. For each semidisc you know its radius and the coordinate of its center in the xaxis. There may be overlaps or one may be completely inside / outside another semidisc.
There are q queries. In each query you will be given a circle with radius r and center C at coordinates (x, y). It is guaranteed that y ≥ r (meaning that no part of the circle is below the xaxis). You need to find the area within the circle which is black. Meaning, area of the circle which is overlapping with some part of any semidisc.
Input
 The first line contains a single integer, T, which denotes the number of testcases. The description of each testcase follows.
 The first line of each testcase contains two spaceseparated integers: n and q, denoting the number of semidiscs and the number of queries respectively.
 The ith of the next n lines contains two spaceseparated integers: x_{i} and r_{i}, denoting that the ith semidisc has its center at (x_{i}, 0) and has radius r_{i}.
 The ith of the next q lines contains three spaceseparated integers: x_{i}, y_{i} and r_{i}, denoting that the ith query circle has its center at (x_{i}, y_{i}) and has radius r_{i}.
Output
 For each query in a testcase, output a single line with the answer.
 Your output will be considered correct if both these are true:
 In each query, the absolute error is less than or equal to 0.02.
 In a single testcase, the average of absolute error over all queries must be less than 0.01.
Constraints
 1 ≤ T ≤ 10
 1 ≤ n ≤ 100000
 20 ≤ q ≤ 200
 1 ≤ all x and y coordinates in the input ≤ 100000
 1 ≤ all radii in input ≤ 100000
 Sum of n over all testcases ≤ 100000
 Sum of q over all testcases ≤ 200
Example
Input: 1 4 2 1 2 2 3 4 2 7 3 7 2 2 8 3 3 Output: 9.3204778956 10.2198951180
Explanation
Note that the example shown above has only two queries (for brief representation) and hence doesn't satisfy the 20 ≤ q constraint. However, in the original test data the constraints will be followed.
The black semidiscs have been colored with various colors for better understanding. And the dotted region represents the region whose area we want to find.
Query 1: The figure below represents the scenario:
Query 2: The figure below represents the scenario:
Author:  triveni 
Editorial  https://discuss.codechef.com/problems/DISCAREA 
Tags  acm17kgp, convexhulltrick, geometry, hard, kgp17rol, montecarlo, triveni 
Date Added:  25112017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 