Description
You are making a figure for your statistics homework, and you
have decide to represent some probabilities using a Venn diagram.
You diagram will consist of 2 circles whose area represent the
probability of 2 different events occurring. As it so happens the
circles have equal radii (the probabilities of the 2 events were
equal). The two circles will intersect the area between them will
represent the probability of both events occurring at the same time.
You want to be as accurate as humanly possible with regards to the intersection between the two
circles. You want to know how far apart you should place the circle to achieve such a goal. Luckily
you have learned binary search recently, so you feel confident in your ability to achieve an accurate
diagram.
Input Specification
You will be given 2 numerical values. The first will be a positive integer, r (r ≤ 1,000), representing
the radius of the circles. The second value will be a positive floating point, a (a < πr
2
), representing
the area that should be in the overlap of the two circles.
Output Specification
Output a single floating point value, d, representing the distance in units required between the two
circles’ centers of radius r units that gives an overlap of size exactly equal a units2
. Answers within
0.0001 units (absolute or relative) of the actual answer will be consider correct.
Input Output Example
Input Output
10 0.0001 19.999174515
1 1.570796326795 0.807945506599
Explanation
Case 1
These circles have very little overlap, so their distance is almost 2 times the radius.
Case2
The value input give circles of radius 1 and the area requested is approximately half the area of a
unit circle (0.5π). For this reason the resulting answer is approximately the offset by which two
circles overlap by half their radius (DDHA), multiplied by the radius (1). Multiplying the given
radius by some constant R and the given area by R
2 will scale the answer by exactly R.
Grading Information
No extra input – 10 points
White space, comments, and variable names – 15 points
r
r
a
d
Binary Searching over the distance – 10 points
Using some Math.h function(s) (atan2, sqrt, fabs, etc.). Use at least one and however many you
feel you need after that – 5 points
Computing the overlapping area between two intersecting circles – 10 points
Your program will be tested on 10 test cases – 5 points each
No points will be awarded to programs that do not compile.
Solutions without binary search will receive a maximum of 50 points
Geometry Hints/Spoilers
For those of you who don’t have the strongest geometry/trigonometry background lets cover a few
geometric properties that can assist you with the math.
First let’s talk about the area of a triangle. Many of you know the one half base times height
formula, but without knowledge of the exact height what can be done. Suppose we know two side
lengths and the angle between them. We can treat one length as the base of the triangle and the
height should be perpendicular to the base. With this information we can make a height by using
some trigonometric properties of right triangles. See the example the line c is formed from the
right triangle with b as the hypotenuse. The length of c must be b times the sin of the angle between
a and b. Since c is perpendicular to a. The height of the triangle with a as the base is c. Thus the
area of the triangle is 1
2
𝑎𝑏 sin 𝜃.
a
b
θ
c
The next part that is very important is related to finding parts of the area of a circle. Suppose we
wanted to know the area of a slice of a pizza, but we only know the radius and the number of slice
(which should be equal in size). This make finding the area very easy. We could find the area using
the standard formula (one half pi radius squared) and divide by the number of slices. For the below
example the area is one eighth the original area.
Suppose we want to know the area of multiple slices, assuming they are of equal size we could
multiply the area of one slice by the number of slices we need to consider. The area below is three
times one eighth the original area (or three eighths the original area).
Following this let’s consider a situation in which each slices angle is exactly one degree. To find
the area of a circular “sector” with angle equal to some integral degree q what would we do? We
could find the area of the circular sector that comprises of only one degree which we can think of
as our slice’s area (this means the slice’s area is one 360th of the original circle’s area or pi times
the radius squared over 360). Then multiply by the number of slices we need, which happens to be
q. In other words the sector’s area is q times pi times radius squared over 360.
As it so happens this works for non-integral q as well (i.e. if q is one half, then the slice’s area is
one half the area of a circular sector whose angle is 1 degree).
The last thing that can help you with this project is try to consider the area of a circular “sector”
as the addition of two different areas. One is a triangle the other is the area of a circular “segment”.
In the following example the circular segment (B) is the circular sector (A+B) minus the triangle
(A),
A B
As it so happens the area of the circular segment (B) can be used to find the overlap between two
circles. Suppose we have two circles (of equal radius) whose centers are separated by distance d.
Then we can compute the area of overlap between them as the area under two different chords of
equal area. One of these chords is in the first circle and the other is in the second. In the below
picture the overlapping area is equal two twice the area section containing the horizontal lines.
Math.h
A source file you might find quite useful is
includes) the line “#include
sqrt(x) which finds the square root of the given parameter x,
sin(x)/cos(x) which return the sine/cosine of an angle x in radians,
asin(x)/acos(x) which returns in radians the arc sine/arc cosine of a value x ∈ [0.0, 1.0].
As it so happens atan2 is one of the better functions for computing the numerical theta value in
radians for some angle. The method takes in two parameters the y and the x component of the
angle. This prevents division by 0, and can give a more precise angle about something by using a
range of [-pi, pi].