TrianglePainting | Topcoder Archive

Problem Statement

Cat Noku has a list of N paintbrushes to use for his next masterpiece. The paintbrushes are labeled from 0 to N-1, and are described by the int[]s x1,y1,x2,y2. Each paintbrush is a nondegenerate triangle. The vertices of paintbrush i have coordinates (0,0), (x1[i],y1[i]), (x2[i],y2[i]).

Noku will go through his paintbrushes from 0 to N-1 and he will use the int[] prob to help him paint his masterpiece. Initially his masterpiece is a single point. He repeats the following procedure for each paintbrush.

He chooses to use paintbrush i with probability prob[i] / 100.
If he chooses to use the paintbrush i, he will place the brush (without rotating it) so that the point (0,0) of the paintbrush will lie somewhere on the boundary of his current masterpiece.
He will then make a stroke with the paintbrush. During the stroke, the brush will move (again, without any rotation) around the entire boundary of the current masterpiece in such a way that the point (0,0) of the paintbrush always lies on the boundary of the current masterpiece. The region painted by the stroke is added to the masterpiece.

Compute and return the expected area of Noku's final masterpiece.

Definition

Class:: TrianglePainting
Method:: expectedArea
Parameters:: int[], int[], int[], int[], int[]
Returns:: double
Method signature:: double expectedArea(int[] x1, int[] y1, int[] x2, int[] y2, int[] prob)
(be sure your method is public)

Notes

Your return value must have an absolute or relative error smaller than or equal to 1e-6.

Constraints

N will be between 1 and 2,500, inclusive.
x1,y1,x2,y2,prob will each have exactly N elements.
Each element of x1,y1,x2,y2 will be between -100 and 100, inclusive.
Each triangle will have a positive area.
Each element of prob will be between 1 and 100, inclusive.

Examples

```
{1,-2,-4}
```
```
{2,3,-1}
```
```
{2,2,-2}
```
```
{-1,-1,1}
```
```
{100,100,100}
```
```
Returns: 52.5
```
Cat Noku has the following paintbrushes: All the paintbrushes will be used. The final masterpiece will look as follows: Note that in the drawing of the final masterpiece each color represents just the area added to the masterpiece after using the brush of the corresponding color, and not the area actually painted by that brush.

{1,-2,-4}

{2,3,-1}

{2,2,-2}

{-1,-1,1}

{50,50,50}

Returns: 15.0

```
{1}
```
```
{1}
```
```
{1}
```
```
{-1}
```
```
{1}
```
```
Returns: 0.01
```

{1,1,1,1,1,1,1,1,1,1}

{-1,1,-1,1,-1,1,-1,1,-1,1}

{1,1,1,1,1,1,1,1,1,1}

{1,-1,1,-1,1,-1,1,-1,1,-1}

{10,20,30,40,50,60,70,80,90,100}

Returns: 31.899999999999995

{-6,-2,-10,9,8,-1,10,5,7,3}

{-5,2,-5,6,6,-10,8,7,-4,-5}

{5,-1,-1,-8,6,7,10,-6,6,3}

{0,-5,-7,4,10,0,10,-3,-3,-4}

{71,100,43,59,51,41,11,53,3,27}

Returns: 940.1964999999999

{34,-71,19,78,69,-73,27,64,-100,70,-87,50,8,-97,46,-46,-30,-40,-30,-23,77,81,48,93,-40,70,
37,-66,53,-87,-85,38,-90,63,-16,24,-2,-60,-88,67,-56,-8,-80,-19,-84,35,95,-24,-26,-15}

{58,-24,-80,33,-98,61,99,79,-34,29,-1,-70,70,90,43,25,-50,-54,73,18,36,8,41,3,26,-6,-80,
-22,65,33,-100,-1,80,-19,-6,-8,-4,-86,-43,-34,0,-93,-61,92,74,-77,32,-78,-56,-21}

{-78,-100,-1,27,67,-31,-82,-24,44,-26,12,36,-36,-71,-84,3,59,28,-26,-79,-47,56,-75,-44,
-85,-72,56,53,-27,53,-19,-65,14,62,96,-44,12,-20,-57,83,59,71,85,-62,21,24,-38,20,52,-64}

{90,-41,79,18,7,-85,-88,-16,12,38,-7,12,-27,-43,-30,-93,48,-19,58,54,70,73,81,89,-35,-75,
63,-73,66,-90,-25,44,-53,59,-14,83,18,-35,-81,49,-11,-63,-87,-92,-83,-43,60,-42,5,-96}

{9,61,1,16,78,4,12,1,17,4,30,28,13,6,4,14,11,6,55,9,66,5,14,8,
70,3,2,6,3,15,8,1,2,12,1,20,37,1,3,66,3,11,2,1,21,2,1,1,27,11}

Returns: 306025.109

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.