MALD Contest 1 P6 - Scratch Cat and Painting

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Java 3.0s
Memory limit: 512M

Problem types
Here is the painting if you're interested

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 r_i and a circular hole with radius h_i. He will call his "painting" an abstract masterpiece and sell it at a high price.

The Scratch Cat creates N annuli with the integer attributes: center x_i, center y_i, hole radius h_i, and radius r_i. 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 $1.00 per 10 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!


1 \le N \le 50

0 \le x_i, y_i \le 1\,000

0 \le h_i < r_i \le 1\,000

Subtask 1 [20%]

All h_i = 0.

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain an integer N, the number of annuli.

The next N lines will contain four space-separated integers, an annulus's attributes, x_i, y_i, h_i, and r_i.

Output Specification

Output the cost of ink used, which is a dollar per 10 square units.

Any answer within an absolute error of 10^{-1} will be accepted.

Sample Input 1

3 3 0 2

Sample Output 1


Explanation 1

This annulus is centred at (3, 3) and has a radius of 2 with a hole radius of 0. This means there is no hole, and the annulus is just a circle with a radius of 2. The total coloured area on this canvas is \pi \times 2^2. The cost of ink is then \frac{\pi \times 2^2}{10}. Any output 10^{-1} away from this value will be accepted.

Sample Input 2

5 5 2 4

Sample Output 2


Explanation 2

This annulus is centred at (5, 5) with a radius of 4 and a hole radius of 2. This canvas's total area (black) is \pi \times (4^2-2^2). The cost of ink is then \frac{\pi \times (4^2-2^2)}{10}. Any output 10^{-1} away from this value will be accepted.

Sample Input 3

0 2 6 7
9 0 6 7

Sample Output 3


Explanation 3

It can be proven that the area of these 2 annuli (the black region in the diagram above) is \approx 79.6773.


There are no comments at the moment.