The Scratch Cat wants to become rich by selling paintings, but he can't draw or paint well with his nonexistent paws. He decided to take a shortcut by creating his art digitally and printing them. Unfortunately, he only remembers how to use the circle tool on the Scratch Costume Editor™. He doesn't remember how to change the colour of his shapes either. The circle tool allows him to create filled circles with any radius and position.
He believes that creating a plain mashup of circles is not creative enough, so he comes up with a genius solution. He will create "donuts" (annuli) instead of circles. The Scratch Cat's annuli have radius and a circular hole with radius . He will call his "painting" an abstract masterpiece and sell it at a high price.
The Scratch Cat creates annuli with the integer attributes: center , center , hole radius , and radius . The Scratch Cat needs to know the approximate cost of ink he needs for his painting since the ink is very expensive. The cost of ink is per square units, and the ink used is the area of the union of shapes he created. Unfortunately, he can't even count to ten (no fingers or toes) and
forces asks you to help!
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line will contain an integer , the number of annuli.
The next lines will contain four space-separated integers, an annulus's attributes, , , , and .
Output the cost of ink used, which is a dollar per square units.
Any answer within an absolute error of will be accepted.
Sample Input 1
1 3 3 0 2
Sample Output 1
This annulus is centred at and has a radius of with a hole radius of . This means there is no hole, and the annulus is just a circle with a radius of . The total coloured area on this canvas is . The cost of ink is then . Any output away from this value will be accepted.
Sample Input 2
1 5 5 2 4
Sample Output 2
This annulus is centred at with a radius of and a hole radius of . This canvas's total area (black) is . The cost of ink is then . Any output away from this value will be accepted.
Sample Input 3
2 0 2 6 7 9 0 6 7
Sample Output 3
It can be proven that the area of these annuli (the black region in the diagram above) is .