SetOfBoxes | Topcoder Archive

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 1.0 0.1"}
```
```
1
```
```
Returns: 5.0E-5
```
```
{"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.

{"0.0 10.0 0.20", "0.100 0.90 20.100", "50.50 60.60 50.70", "51.55 55.60 51.65"}

Returns: 0.028

{"0.0 10.0 0.20", "0.100 0.90 20.100", "50.50 60.60 50.70", "51.55 55.60 51.65"}

Returns: 0.97

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.