Problem Statement
You and another baker are working on cutting a w x h sheet cake into pieces. Each piece must be a w1 x h1 rectangle with sides parallel to the sides of the cake. Note that the pieces cannot be rotated: the width of the piece must run in parallel to the width of the cake.
Your coworker does not like to work in any orderly fashion. He has decided to cut out the first piece completely at random. More precisely, he will choose the location of the top left corner of the cut uniformly at random from all possible locations such that the entire cut lies within the cake. (Note that the coordinates may be arbitrary real numbers, not just integers.)
Calculate the probability that after his cut you will still be able to cut out at least one more piece of the same size.
Definition
- Class:
- EvilCakeCutter
- Method:
- successProbability
- Parameters:
- int, int, int, int
- Returns:
- double
- Method signature:
- double successProbability(int w, int h, int w1, int h1)
- (be sure your method is public)
Constraints
- w1 will be between 1 and w, inclusive.
- h1 will be between 1 and h, inclusive.
- w will be between w1 and 1,000,000, inclusive.
- h will be between h1 and 1,000,000, inclusive.
Examples
3
2
1
1
Returns: 1.0
It's always possible to get a second piece.
2
2
1
1
Returns: 0.0
The only way a second piece can be cut, is if the first piece comes perfectly from a corner, or perfectly along the edge. Since the evil cut is chosen continuously, the probability of this is infinitesimally small.
8
5
3
2
Returns: 0.9333333333333333
Only if the first cut is right near the middle, leaving too small a width or height anywhere around it, can a second piece not be cut. In most cases getting a second piece is possible.
1000000
1000000
345678
456789
Returns: 0.9614101733636184
58
45
23
19
Returns: 0.8549450549450549
21097
93306
17119
59877
Returns: 0.0
52756
55913
11647
13768
Returns: 1.0
55882
42224
10244
33854
Returns: 1.0
70866
64200
34317
15962
Returns: 1.0
57564
35944
24067
18572
Returns: 0.5630354957160343
20086
37857
8150
4181
Returns: 1.0
14418
16242
3594
9224
Returns: 1.0
26424
71047
7761
10261
Returns: 1.0
34485
58786
24575
14134
Returns: 1.0
40451
93771
789
36763
Returns: 1.0
39311
63462
16301
24289
Returns: 0.8999160312205834
50273
36106
38954
25466
Returns: 0.0
50965
39645
18108
34794
Returns: 0.8977691207353076
86738
44569
44076
29104
Returns: 0.0
47893
53776
25148
32857
Returns: 0.0
21335
51665
10096
23450
Returns: 0.4724617420633642
36196
1914
14172
1676
Returns: 0.7130403196512896
29601
41846
16872
16562
Returns: 0.689922480620155
735
27463
369
15142
Returns: 0.0
76970
32019
38665
30545
Returns: 0.0
2
2
2
2
Returns: 0.0
1
1
1
1
Returns: 0.0
1
10
1
4
Returns: 0.6666666666666666
1000000
1000000
1
1
Returns: 1.0
5
1
2
1
Returns: 0.6666666666666666
10
19
8
9
Returns: 0.19999999999999996
30
20
11
10
Returns: 0.8421052631578947
5
17
5
7
Returns: 0.6
81
35
29
33
Returns: 0.8846153846153846
1000000
1000000
999999
999999
Returns: 0.0
1000000
1000000
500000
500000
Returns: 0.0
100
5
5
5
Returns: 1.0
1
5
1
2
Returns: 0.6666666666666666
5
5
3
2
Returns: 0.6666666666666666
80
5
5
5
Returns: 1.0
557679
209397
62005
109981
Returns: 1.0
1
5
1
1
Returns: 1.0
10
5
4
2
Returns: 0.8888888888888888
999
999
999
999
Returns: 0.0
2
3
2
1
Returns: 1.0
1000000
1000000
500000
300000
Returns: 1.0