TopCoder problem "BlackWhitePlane" used in SRM 271 (Division II Level Two)

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 a String[] 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.

Definition

Class:	BlackWhitePlane
Method:	area
Parameters:	String[]
Returns:	double
Method signature:	double area(String[] circles)
(be sure your method is public)

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

{"1 1 1"}

Returns: 3.141592653589793

The only circle is drawn on the black plane, so it is white. Its area is pi*R².

{"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*3² + pi*1² - pi*1² = pi*9.

{"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.

{"2549 8482 11", "9175 5927 35", "2747 6177 93", "5512 8791 81", "4487 8456 60",
 "6899 610 77", "9716 2202 3", "9312 5625 79", "4020 9851 85", "1640 7179 54", 
 "5761 4348 51","5917 3436 88","6547 386 33","182 7676 1","6329 4496 89"}

Returns: 194250.95695676407

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4497

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8068&pm=4497

Writer:

Vedensky

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simulation, Sorting