TopCoder problem "SetOfBoxes" used in TCHS SRM 15 (Division I Level Three)



Problem Statement

    You have a large square box and some smaller triangular boxes (all two-dimensional). The triangular boxes all lie inside the square box. Triangular boxes may lie inside other triangular boxes, but they must not overlap. You randomly throw an object (represented as a point) into the square box, and you want to know if it lands inside exactly inBox triangular boxes.



You are given a String[] boxes, each element of which is formatted as "X1.Y1 X2.Y2 X3.Y3" (quotes for clarity only), representing the three corners of a triangular box. The large square box has sides parallel to the axes, and has corners at (0, 0) and (100, 100). Return the probability (between 0 and 1) that a random point within the square is contained in exactly inBox triangular boxes.
 

Definition

    
Class:SetOfBoxes
Method:countThrow
Parameters:String[], int
Returns:double
Method signature:double countThrow(String[] boxes, int inBox)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-boxes will contain between 0 and 50 elements, inclusive.
-Each element of boxes will be formatted as "X1.Y1 X2.Y2 X3.Y3" (quotes for clarity only).
-X1, Y1, X2, Y2, X3, Y3 will be integers with no leading zeros, each between 0 and 100, inclusive.
-Triangles represented by different elements of boxes will have no common points.
-inBox will be between 0 and 50, inclusive.
 

Examples

0)
    
{"0.0 1.0 0.1"}
1
Returns: 5.0E-5
1)
    
{"0.0 20.0 0.10", "1.1 6.1 1.5"}
1
Returns: 0.0090
Here it is the area of the first triangle minus the area of the second one.
2)
    
{"0.0 10.0 0.20", "0.100 0.90 20.100", "50.50 60.60 50.70", "51.55 55.60 51.65"}
1
Returns: 0.028
3)
    
{"0.0 10.0 0.20", "0.100 0.90 20.100", "50.50 60.60 50.70", "51.55 55.60 51.65"}
0
Returns: 0.97

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10067&pm=6596

Writer:

Vedensky

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Geometry, Graph Theory, String Parsing