Problem Statement
There are two buildings opposite each other as in the figure below.
On the left building, there is a rectangular window, with the lower
and upper sides given by ylow and yhigh (the y-coordinate
as shown in the image: starting with 0.0 at the bottom and increasing
upwards). On the building on the opposite
side there is also a window, but it is not necessarily rectangular. Its shape
is a convex polygon, with the x- and y-coordinates (as
shown in the image: x-coordinate increasing to the back, y-coordinate starting
with 0.0 at the bottom and increasing upwards) of the corners given by the
A frog lies at some point on the window of the left building, and a fly lies at some point on the window of the right building. Assuming that the frog and fly are positioned randomly (uniformly) at some point on the windows, what is the probability that the frog can see the fly (i.e., the line of sight between them does not cross the wall)?
Definition
- Class:
- FrogAndFly
- Method:
- visibility
- Parameters:
- int, int, int, int, int, int[], int[]
- Returns:
- double
- Method signature:
- double visibility(int hwall, int dfrog, int dfly, int ylow, int yhigh, int[] xwindow, int[] ywindow)
- (be sure your method is public)
Notes
- The return value must be within 1e-9 absolute or relative error of the actual result.
Constraints
- hwall will be between 0 and 100, inclusive.
- dfrog will be between 1 and 100, inclusive.
- dfly will be between 1 and 100, inclusive.
- ylow will be between 0 and 100, inclusive.
- yhigh will be between 0 and 100, inclusive.
- ylow will be smaller than yhigh.
- xwindow and ywindow will have between 3 and 50 elements, inclusive.
- xwindow and ywindow will have the same number of elements.
- Each element of xwindow will be between 0 and 100, inclusive.
- Each element of ywindow will be between 0 and 100, inclusive.
- The polygon defined by the coordinates represented by the elements of xwindow and ywindow will be a convex polygon with non-zero area. There will be no two identical points, and no three points will be collinear.
Examples
10
10
10
5
15
{5, 5, 15, 15}
{5, 15, 15, 5}
Returns: 0.5
The windows on both sides are rectangular with the lower sides at height 5 and the upper sides at height 15. The wall is exactly in the middle between the buildings and has a height of 10. Due to the symmetric configuration, the probability of the fly being visible by the frog here is exactly 0.5 (50%).
14
10
10
5
15
{5, 5, 15, 15}
{5, 15, 15, 5}
Returns: 0.02
The same situation as above, just the wall has now a height of 14. If both the fly and the frog are above a height of 13, we have a symmetric configuration again with probability 0.5 of the fly being visible by the frog. If the frog or the fly (or both) is below a height of 13, the fly will not be visible by the frog. The probability of both being above a height of 13 is 0.2 * 0.2 = 0.04, so the total probability is 0.04 * 0.5 = 0.02.
10
5
10
5
15
{10, 20, 15}
{5, 5, 15}
Returns: 0.4166666666666665
A triangular window.
0
1
20
10
100
{0, 10, 20, 30, 15}
{20, 10, 10, 20, 40}
Returns: 1.0
The wall has height 0, so even from the lowest point (ylow) the frog can always look at the fly.
100
30
10
20
40
{10, 20, 30, 20}
{20, 10, 20, 30}
Returns: 0.0
The wall is now too high and hides the whole opposite window, so the frog can never look directly at the fly.
100
23
45
0
100
{10, 20, 20, 10}
{5, 10, 100, 100}
Returns: 0.0
50
20
40
40
60
{0, 0, 100, 100}
{0, 30, 30, 0}
Returns: 0.0
10
50
10
60
100
{0, 10, 30, 40, 20}
{0, 30, 50, 30, 0}
Returns: 1.0
40
20
30
10
50
{0, 0, 10, 25, 75, 90, 100, 100, 90, 75, 25, 10}
{75, 25, 10, 0, 0, 10, 25, 75, 90, 100, 100, 90}
Returns: 0.4448559670781891
50
100
100
0
100
{20, 30, 40}
{10, 90, 50}
Returns: 0.5
50
100
100
40
60
{20, 30, 40}
{10, 90, 50}
Returns: 0.5
30
1
100
0
100
{1, 1, 2, 2}
{1, 2, 2, 1}
Returns: 0.6971499999999875
50
100
1
0
100
{10, 30, 20}
{45, 45, 55}
Returns: 0.25083333333333335
50
10
10
43
87
{50, 58, 65, 71, 76, 80, 83, 85, 86, 87, 88, 89, 90, 91, 92, 93, 93, 92, 91, 90, 89, 88, 87, 86, 85, 83, 80, 76, 71, 65, 58, 50, 49, 41, 34, 28, 23, 19, 16, 14, 13, 12, 11, 10, 9, 8, 7, 6, 6, 7}
{ 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 19, 23, 28, 34, 41, 49, 50, 58, 65, 71, 76, 80, 83, 85, 86, 87, 88, 89, 90, 91, 92, 93, 93, 92, 91, 90, 89, 88, 87, 86, 85, 83, 80, 76, 71, 65, 58, 50, 49, 41}
Returns: 0.7312884765428392
53
65
85
50
87
{1, 3, 35, 64, 79, 96, 98, 98, 88, 45, 1}
{41, 0, 0, 2, 5, 27, 54, 76, 96, 99, 98}
Returns: 0.6920380290710596
27
25
80
13
34
{0, 5, 11, 26, 72, 81, 90, 97, 99, 99, 98, 92, 47, 4}
{88, 29, 5, 4, 1, 1, 13, 23, 48, 67, 87, 100, 100, 99}
Returns: 0.6546875875058483
84
87
61
12
70
{0, 3, 66, 93, 100, 100, 92, 80, 51, 29, 9, 2}
{55, 2, 7, 12, 53, 70, 88, 97, 99, 100, 81, 62}
Returns: 0.0019548653190851763
73
12
7
56
88
{0, 99, 100, 100, 94, 21, 9}
{1, 4, 81, 98, 100, 100, 99}
Returns: 0.261934327475873
76
26
84
4
25
{0, 2, 12, 34, 45, 83, 93, 99, 100, 95, 89, 35}
{98, 41, 7, 3, 2, 1, 1, 35, 67, 93, 100, 100}
Returns: 0.0
37
1
53
33
43
{0, 1, 2, 7, 18, 94, 96, 100, 85, 75, 1}
{97, 50, 11, 3, 0, 4, 18, 84, 95, 100, 99}
Returns: 0.6259195009356726
40
6
55
0
47
{3, 4, 8, 57, 86, 100, 100, 95, 85, 70, 60, 20, 13}
{80, 6, 3, 0, 0, 7, 68, 87, 99, 100, 100, 96, 95}
Returns: 0.16938127855339807
13
3
3
78
89
{0, 3, 7, 32, 46, 90, 99, 100, 100, 98, 65, 35, 7}
{27, 9, 6, 1, 1, 2, 35, 55, 71, 91, 97, 100, 94}
Returns: 1.0
2
98
66
17
64
{0, 2, 6, 57, 87, 95, 99, 98, 90, 51, 30, 15, 6, 1}
{44, 5, 3, 1, 1, 10, 30, 82, 98, 100, 100, 99, 98, 87}
Returns: 1.0
5
86
54
16
99
{1, 3, 9, 27, 50, 80, 98, 100, 87, 55, 30, 6}
{85, 24, 7, 3, 0, 2, 10, 58, 96, 100, 99, 97}
Returns: 0.9999999999999998
34
8
71
45
94
{1, 2, 85, 92, 100, 100, 97, 38, 9, 1}
{25, 2, 5, 7, 11, 48, 98, 94, 91, 85}
Returns: 1.0
85
100
61
46
47
{0, 1, 2, 16, 89, 99, 100, 79, 65, 1, 0}
{57, 15, 5, 0, 0, 2, 84, 94, 100, 95, 80}
Returns: 0.0
41
44
40
1
90
{1, 2, 36, 95, 100, 99, 81, 45, 6, 3, 2}
{22, 6, 0, 2, 24, 91, 100, 100, 98, 83, 53}
Returns: 0.6344289648789734
40
33
32
12
60
{3, 6, 10, 45, 79, 96, 100, 98, 96, 37, 3}
{63, 13, 0, 0, 3, 12, 42, 96, 99, 100, 94}
Returns: 0.5759033833442064
48
37
16
44
81
{0, 4, 28, 85, 93, 99, 99, 97, 89, 17, 0}
{20, 8, 0, 0, 10, 37, 85, 91, 100, 100, 97}
Returns: 0.5993962766833667
51
78
40
16
96
{1, 13, 20, 81, 90, 96, 98, 90, 85, 29, 19, 7, 1}
{12, 5, 3, 0, 1, 43, 89, 96, 99, 100, 100, 99, 50}
Returns: 0.5257135440303358
69
11
5
20
47
{1, 6, 15, 54, 93, 97, 100, 98, 78, 24, 4}
{49, 5, 4, 0, 0, 9, 19, 93, 100, 96, 85}
Returns: 0.11476783219457962
9
32
16
57
95
{0, 4, 60, 93, 97, 100, 92, 55, 3, 1, 0}
{14, 0, 3, 7, 16, 52, 97, 99, 100, 91, 81}
Returns: 1.0
78
61
62
1
9
{0, 4, 9, 89, 98, 99, 98, 90, 66, 31, 6, 3}
{16, 3, 3, 4, 5, 43, 59, 90, 100, 99, 94, 71}
Returns: 0.0
53
74
87
30
45
{0, 1, 4, 10, 59, 91, 95, 100, 99, 98, 83, 73, 6}
{94, 60, 31, 0, 2, 4, 27, 69, 85, 88, 97, 98, 96}
Returns: 0.2788174537911814
0
40
19
6
76
{2, 10, 20, 98, 100, 98, 48, 5, 4, 3}
{12, 0, 0, 4, 23, 90, 100, 99, 81, 51}
Returns: 1.0
11
6
22
38
94
{0, 78, 83, 99, 99, 80, 10, 4, 0}
{4, 2, 4, 26, 82, 95, 96, 93, 45}
Returns: 0.9999999999999999
15
40
71
7
78
{0, 57, 100, 94, 14, 5, 1}
{0, 0, 7, 100, 100, 97, 77}
Returns: 0.96771995663966
87
57
65
2
65
{0, 1, 34, 98, 100, 100, 80, 27, 1, 0}
{49, 2, 1, 7, 15, 31, 98, 93, 83, 82}
Returns: 0.0
55
32
9
33
39
{0, 4, 23, 69, 96, 97, 84, 76, 13, 1, 0}
{48, 10, 2, 0, 16, 78, 90, 97, 95, 83, 69}
Returns: 0.3739715387351736
53
18
39
40
67
{0, 3, 21, 97, 100, 100, 88, 7, 0}
{46, 0, 0, 3, 70, 91, 98, 91, 90}
Returns: 0.4616293016303041
0
24
58
39
54
{0, 1, 10, 81, 95, 98, 100, 99, 93, 37, 11, 6, 5}
{48, 10, 2, 0, 1, 6, 23, 70, 95, 98, 96, 91, 87}
Returns: 1.0
59
1
2
8
67
{1, 2, 8, 94, 98, 98, 95, 83, 73, 15, 1}
{38, 11, 0, 0, 10, 74, 83, 95, 99, 95, 94}
Returns: 0.12271609628922586
16
92
5
13
47
{0, 1, 15, 28, 75, 81, 100, 100, 85, 2}
{28, 9, 4, 3, 2, 2, 7, 81, 100, 94}
Returns: 0.8735652214379483
90
68
28
50
63
{1, 2, 12, 24, 72, 76, 91, 99, 97, 93, 26}
{91, 50, 10, 1, 1, 2, 9, 47, 95, 97, 100}
Returns: 0.0
75
12
37
7
31
{0, 1, 83, 100, 99, 98, 92, 85, 1}
{46, 0, 0, 50, 86, 94, 97, 98, 100}
Returns: 0.0
74
9
57
6
22
{1, 6, 12, 37, 84, 98, 98, 60, 40, 6, 3, 1}
{15, 8, 1, 2, 5, 11, 100, 99, 98, 95, 91, 59}
Returns: 0.0
64
58
86
87
89
{0, 1, 9, 67, 93, 99, 98, 95, 93, 75, 16, 9}
{90, 16, 7, 4, 5, 9, 36, 67, 86, 96, 100, 100}
Returns: 0.7456110582621194
3
22
62
23
73
{2, 10, 13, 34, 90, 100, 95, 33, 10, 4, 2}
{10, 2, 1, 1, 2, 22, 100, 100, 97, 95, 20}
Returns: 1.0
20
43
82
19
99
{0, 1, 4, 31, 85, 98, 99, 97, 78, 27, 3, 1, 0}
{45, 15, 1, 0, 0, 5, 14, 89, 100, 95, 90, 76, 62}
Returns: 0.9843522430679414
45
99
48
15
57
{2, 8, 9, 67, 92, 100, 100, 99, 92, 14, 10, 2}
{27, 3, 2, 0, 3, 9, 52, 92, 97, 100, 99, 35}
Returns: 0.4967914799751301
99
84
63
8
63
{1, 31, 61, 97, 100, 96, 25, 9, 3, 1}
{6, 0, 0, 5, 86, 100, 100, 93, 82, 50}
Returns: 0.0
50
71
81
70
73
{0, 3, 10, 76, 85, 90, 99, 100, 93, 85, 69, 9}
{50, 29, 0, 1, 4, 12, 34, 46, 91, 96, 99, 100}
Returns: 0.7679828504831434
31
20
94
23
72
{0, 1, 6, 37, 63, 75, 86, 98, 100, 97, 12}
{95, 33, 3, 1, 0, 0, 1, 12, 51, 99, 100}
Returns: 0.9018835101930563
80
5
48
32
51
{0, 21, 85, 99, 100, 99, 80, 36, 18, 0}
{13, 4, 0, 11, 69, 82, 96, 100, 100, 98}
Returns: 0.0