Polar rectangles#3148
Vasya has recently learned about the polar coordinate system, particularly the concept of a polar rectangle. On a Cartesian plane, if two concentric circles with center at the origin are drawn, the region between them is called a ring (illustrated in blue in the figure). If two rays are drawn from the origin, the area swept out from the first ray to the second (moving in a counterclockwise direction, i.e., increasing angles) is referred to as an angle (the area between these two rays, shown in green). A polar rectangle is defined as the intersection of an angle and a ring (highlighted in red).
Several polar rectangles are given. Find the area of their intersection. Note that the intersection of polar rectangles may consist of several parts!
The first line contains an integer — the number of rectangles (1 \leq N \leq 100000). The next lines contain the descriptions of the rectangles. Each rectangle is described by four real numbers: r_1, r_2, \varphi_1, \varphi_2. Here, r_1 and r_2 are the radii of the circles forming the ring (r_1 < r_2), and \varphi_1, \varphi_2 are the angles (in radians) formed by the first and second rays with the -axis. The area is swept from the first ray to the second in a counterclockwise direction (i.e., as the angle increases), even if \varphi_1 > \varphi_2. All numbers are given with up to six decimal places. The angles are within the half-open interval [0, 2\pi), and the radii do not exceed 10^6. It is guaranteed that \varphi_1 \ne \varphi_2.
Output a single number — the area of the desired intersection. Your answer will be considered correct if its absolute or relative error does not exceed 10^{-6}.
Example 1