Hunter Liu's Website

The set of points in the circle of radius \(r\) centred at the point \(\left( x_2, y_2 \right)\) is precisely the set of points a distance of at most \(r\) from that point. In other words, the point \(\left( x_1,y_1 \right)\) is in our circle if its distance to the centre is less than \(r\). Let’s write the pseudocode for this problem:

1. Set \(\left( x_1, y_1 \right)\) equal to the first pair of inputted numbers.
2. Set \(\left( x_2, y_2 \right)\) equal to the next pair of inputs.
3. Set \(r\) equal to the last input.
4. Compute \(d\), the distance between the two points, with the distance formula: \(d=\sqrt{\left( x_1-x_2 \right)^2+\left( y_1-y_2 \right)^2}\).
5. If \(d>r\), then the point is not inside the circle. Otherwise, the point is inside the circle. Print the corresponding statement.

Here’s the solution in code:

 1#include <iostream>     // needed for cout, cin, endl 
 2#include <cmath>        // we need to take a squareroot! 
 3
 4using namespace std; 
 5
 6int main() {
 7    double x1, y1, x2, y2, r; 
 8    cin >> x1 >> y1;    // step 1 - collecting first point 
 9    cin >> x2 >> y2;    // step 2 - collecting centre of circle 
10    cin >> r;           // step 3 - collecting radius of circle 
11
12    // step 4 - computing distance between the two points. 
13    double d = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); 
14
15    // step 5 - output the statement corresponding to whether or not
16    // d <= r. Can you see why this snippet works the way we want it
17    // to? We are avoiding redundancy by *only* keeping the output
18    // that depends on d <= r inside the if statement. 
19    cout << "The point (" << x1 << ", " << y1 << ") is "; 
20
21    if(d > r) {
22        cout << "not "; 
23    } 
24
25    cout << "contained in the circle of radius " << r 
26         << " centred at the point (" << x2 << ", " << y2 << ")." 
27         << endl; 
28
29    return 0; 
30}

Let \(a, b, c\) be the three numbers the user inputs. This problem would be pretty easy if \(a\geq b \geq c\) or \(a\leq b\leq c\): we just need to compare if \(b-a\) and \(c-b\) are equal. However, what happens if the three are out of order?

In other words, we need to worry about what happens if \(b\) is either smaller than or bigger than both \(a\) and \(c\). We should rearranged the three numbers so that they’re in order. In pseudocode, here’s our strategy:

1. Read three integers \(a, b, c\) from user input
2. Rearrange these three integers so they’re in increasing or decreasing order.
3. Compute the differences \(b-a\) and \(c-b\). (Do we need them to have absolute values if everything’s in order?)
4. If the two differences are equal, print “Evenly spaced”.
5. If the two differenecs are unequal, print “Unevenly spaced”.

Can you think of an algorithmic strategy to implement step 2?

Here is a solution that we came up in class. Our strategy for step 2 was as follows:

• If \(b\) was greater than both \(a\) and \(c\)…
  • If \(c > a\), then swap \(b\) and \(c\).
  • Otherwise, swap \(b\) and \(a\).
• If \(b\) was smaller than both \(a\) and \(c\)…
  • If \(c > a\), then swap \(b\) and \(a\).
  • Otherwise, swap \(b\) and \(c\).

Read through these cases carefully, and try working them out with specific inputs to see why this works. This is what the full solution ended up being:

 1#include <iostream>     // needed for cin, cout, endl 
 2
 3using nampsace std; 
 4
 5int main() {
 6    // step 1: reading input 
 7    int a, b, c; 
 8    cin >> a >> b >> c; 
 9
10    // step 2: reordering. See the above outline for details.
11    // to swap two variables, we need an auxiliary variable 
12    // (usually called temp) to "remember" what one variable is
13    // before overwriting. 
14    if(b > a && b > c) {        // b is the largest 
15        if(c > a) {
16            int temp = b; 
17            b = c; 
18            c = temp; 
19        } else {
20            int temp = b; 
21            b = a; 
22            a = temp; 
23        }
24    } else if(b < a && b < c) { // b is the smallest 
25        if(a < c) {
26            int temp = b; 
27            b = a; 
28            a = temp; 
29        } else {
30            int temp = b; 
31            b = c; 
32            c = temp; 
33        }
34    }
35
36    // 3. compute the pairwise differences
37    int space_one = b - a; 
38    int space_two = c - b; 
39
40    // 4 and 5. print output 
41    if(space_one == space_two) {
42        cout << "Evenly spaced" << endl; 
43    } else {
44        cout << "Unevenly spaced" << endl; 
45    }
46
47    return 0; 
48}

Our solution is rather lengthy. Notice how we repeat the line int temp = b; four separate times, and moreover, we repeat the swapping procedures twice each. Can you think of a way to reorganise our if statements so that this doesn’t happen? (This is called refactoring.) The second solution below is a “cleaned up” solution that avoids these redundancies. Try to do it yourself and compare the results!

Rather than thinking of each unfavourable situation and then deciding what to do, we should think about which situations require us to switch \(a\) and \(b\) or \(b\) and \(c\). Specifically,

• We should switch \(a\) and \(b\) when…
  • \(b < a \leq c\) (such as 2 1 3)
  • \(b > a \geq c\) (such as 2 3 1)
• We should switch \(b\) and \(c\) when…
  • \(b < c \leq a\) (such as 3 1 2)
  • \(b > c \geq a\) (such as 1 3 2)

Make sure you understand why these cover all possible arrangements of the user’s input. When we translate this into code, we only need to perform each swap once, though the if statements’ conditions will be slightly hairier. Here’s the cleaner solution:

 1#include <iostream>     // needed for cout, cin, endl 
 2
 3using namespace std; 
 4
 5int main() {
 6    // 1. collect user input 
 7    int a, b, c; 
 8    cin >> a >> b >> c; 
 9
10    // 2. rearrange input as described above. 
11    int temp = b; 
12    if((b < a && a <= c) || (b > a && a >= c)) { // a <-> b
13        b = a; 
14        a = temp; 
15    } else if((b < c && c <= a) || (b > c && c >= a)) { // b <-> c
16        b = c; 
17        c = temp; 
18    }
19
20    // 3. compute the pairwise differences 
21    int space_one = b - a; 
22    int space_two = c - b; 
23
24    // 4 and 5. Determine output 
25    if(space_one == space_two) {
26        cout << "Evenly spaced" << endl; 
27    } else {
28        cout << "Unevenly spaced" << endl; 
29    } 
30
31    return 0; 
32}

Make sure that your program can pass the following test cases:

• \((0, 0)\), \((1, 1)\), and \((2, 2)\) are colinear.
• \((0, 4)\), \((6, 10)\), and \((3, 7)\) are colinear.
• \((-2, 4)\), \((7, 5)\), and \((19, -12)\) are not colinear.
• \((0, 0)\), \((0, 1)\), and \((0, 2)\) are colinear. Note these lie on a vertical line, so the slope of this line is ill-defined.
• \((0, 0)\), \((0, 0)\), and \((0, 0)\) are colinear. Note these are all the same point, so they all lie on multiple different lines through the origin.
• \((0, 0)\), \((3, 3)\), and \((0, 0)\) are colinear. Note two of these points are the same. In addition, \((0, 0)\), \((0, 0)\), and \((3, 3)\) are colinear.
• \((0, 0)\), \((1, 1)\), and \((0, 2)\) are not colinear. Note two of these points lie on a vertical line.

If you missed any of these test cases, particularly the latter three, this likely means you didn’t think about “degenerate cases” or “special cases”. Identifying these special circumstances is a critical skill in programming!

The first two cases use the rectangle \((0, 0), (1, 0), (0, 3), (1, 3)\). Make sure that your program identifies this as a rectangle, no matter which order you input them. The point \((0.5, 1)\) is contained in this rectangle, but the point \((4, 7)\) is not.

The next two cases use the rectangle \((1, 2), (3, 4), (0, 3), (2, 5)\). Make sure your program identifies this as a rectangle, also in any order of input. Note that this is a rectangle whose sides are not parallel to the coordinate axes. The point \((1, 3)\) is inside this rectangle, the point \((2, 3)\) is on its border, and the point \((3, 7)\) is outside it.