MALD Contest 1 P6 - Scratch Cat and Painting
View as PDF
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!
Constraints
Subtask 1 [20%]
All .
Subtask 2 [80%]
No additional constraints.
Input Specification
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 Specification
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
1.2566
Explanation 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
3.7699
Explanation 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
7.9677
Explanation 3
It can be proven that the area of these  annuli (the black region in the diagram above) is 
.
Comments