BlackWhitePlane
SRM 271 · 2005-11-08 · by Vedensky
SRM 271 · 2005-11-08 · by Vedensky · Simulation, Sorting
Problem Statement
Problem Statement
There are some circles on the plane. Circles may lie completely inside other circles, but may not touch or intersect other circles in any other way. Initially, the plane is entirely black. Then circles are drawn in order of non-increasing radii. If a circle is drawn on a black background, it is filled with the color white. If it is drawn on a white background, it is filled black. Your task is to compute the total white area on the plane after drawing all the circles.
You are given aString[] circles containing the circles on the plane. Each element will be formatted as "X Y R", where (X, Y) are the coordinates of the center of the circle, and R is the radius.
You are given a
Notes
- A circle can lie completely inside another circle only if it has a smaller radius than the outer circle.
- The returned value must be accurate to 1e-9 relative or absolute.
Constraints
- circles will contain between 1 and 50 elements, inclusive.
- Each element of circles will be formatted as "X Y R", where X, Y, and R are integers with no leading zeroes.
- Each X and Y will be between 0 and 10000, inclusive.
- Each R will be between 1 and 100, inclusive.
- No two circles in circles will touch or intersect (unless one lies completely inside the other).
Examples
0)
{"1 1 1"}
Returns: 3.141592653589793
The only circle is drawn on the black plane, so it is white. Its area is pi*R2.
1)
{"4 3 1", "3 2 3", "8 1 1"}
Returns: 28.274333882308138
The first circle is drawn inside of the second, so it is black. The total white area is pi*32 + pi*12 - pi*12 = pi*9.
2)
{"15 15 4", "15 25 4", "25 25 4", "25 15 4", "25 25 100"}
Returns: 31214.86460606818
The first four circles are all inside the fifth one.
3)
{"10 10 10", "10 30 9"}
Returns: 568.6282702997526
4)
{"0 0 6", "5 12 6"}
Returns: 226.1946710584651
5)
{"0 0 1", "0 0 2", "0 0 3", "0 0 4", "0 0 5", "0 0 6", "0 0 7", "0 0 8", "0 0 9" ,"0 0 10"}
Returns: 172.78759594743866
Each of the concentric circles changes color.
Submissions are judged against all 71 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BlackWhitePlane with a public method double area(vector<string> circles) · 71 test cases · 2 s / 256 MB per case