A programming challenge all up in your face.

[TheQuirk]

Ladies and gentlemen, it's time for another programming challenge. This one deals with circles and lines, so some math will be required.

A picture is worth a thousand words, so I'll start with an illustration I drew.



Your mission: Find the length of the bold curve.

Input: Your program should read a file called "INPUT," which is in the following format:

x_i
y_i
x_f
y_f
n
x_1 y_1 r_1
x_2 y_2 r_2
...
x_n y_n r_n

Example:
1
10
10
1
1
5 5 4

(x_i denotes the x-coordinate of the BEGINNING of the curve; y_i denotes of y-coordinate of the BEGINNING of the curve; x_f denotes the x-coordinate of the END of the curve; y_f denotes the y-coordinate of the END of the curve; n denotes the number of circles there are; x_j denotes the x-coordinate of the center of circle j; y_j denotes the y-coordinate of the center of circle j; r_j denotes the radius of circle j.)

None of the circles touch or intersect, and all the figures belong to the first quadrant/the two axes.

Output: your program should output the length of the curve to a file called "OUTPUT."

The following math things may prove useful.

The equation of a line with slope a and y-intercept b is y = ax + b.

The slope can be found by taking two points which belong to the line, (x_1, y_1) and (x_2, y_2), and performing the following operation:

Code: [Select]


    y_2 - y_1
a = ---------
    x_2 - x_1

The distance between two points with coordiantes (x_1, y_1) and (x_2, y_2) equals sqrt((x_2 - x_1)^2 + (y_2 - y_1)^2)

The standard equation of a circle of radius r with center at (x_0, y_o) is::

Code: [Select]


(x - x_0)^2 + (y - y_0)^2 = r^2

Note that any positive number has TWO square roots. E.g. sqrt(4) = {-2, 2}, not just 2.

A quadratic equation is an equation in the form ax^2 + bx + c = 0. The solution is this:

Code: [Select]


       -b - sqrt(b^2 - 4ac)
x_1 =  --------------------
                 2a

       -b + sqrt(b^2 - 4ac)
x_2 =  --------------------
                 2a

Note that if b^2 - 4ac > 0, then there are two solutions; if b^2 - 4ac = 0, there is one solution; if b^2 - 4ac < 0, then there are no real solutions. (The expression b^2 - 4ac is called the discriminate, and is usually represented by the capital letter D.)

When making algebraic manipulations, don't forget about the domain! For example, suppose you have to solve the following equation:

Code: [Select]


(sqrt(x))^2 = -15

The answer is "no solution"--NOT -15. The square root function has the domain [0, +inf)!

The formula for the length of an arc is:

Code: [Select]


s = Ar

Where A is the measure of the angle in radians, and r is the radius of the circle.

In addition, I suggest looking up the Law of Cosines (or, alternatively, Pythagorean

[Orethrius]

[offtopic]

Code: [Select]

(sqrt(x))^2 = -15
The answer is "no solution"--NOT -15. The square root function has the domain (0, +inf)!

Not intending to be a nit or anything, but isn't (√x)^2 == x, where x ≥ 0?  Sorry for the tangent, I'm just trying to see if I correctly remember my Calculus classes.

[/offtopic]

[H_TeXMeX_H]

[OFFTOPIC]The square root of anything squared is the absolute value of that something ... meaning a positive number[/OFFTOPIC]

[Pathos]

[offtopic]


Not intending to be a nit or anything, but isn't (√x)^2 == x, where x ≥ 0?  Sorry for the tangent, I'm just trying to see if I correctly remember my Calculus classes.

[/offtopic]

If you use complex numbers it works, if you algebraically cancel the two operations out it works. If you attempt the find the Real root your screwed.

[Pathos]

Will the circles ever overlap the end points of the line?

[Orethrius]

If you use complex numbers it works, if you algebraically cancel the two operations out it works. If you attempt the find the Real root your screwed.

You have already lost.
The correct answer is always "42."

Having said that, 42.   QED.

[piratePenguin]

http://illhostit.com/files/3913162470455711/curve_q.png
Whenever the curve is going around a circle it can go around it clockwise or anti-clockwise, does it always go clockwise or should it go for the shortest route?

[TheQuirk]

Shortest route, and no, the circles don't overlap.

About the (sqrt(x))^2 = x thing: for x >= 0, yes, (sqrt(x))^2 = x is correct. What a lot of people do, though, is forget that the square root function has a domain of [0; inf) and solve things like (sqrt(x))^2 = -1 in the real number system.

[TheQuirk]

Let's take this thing apart piece  piece!

Before we write any code, we have to answer a few questions:

a) How do we represent the line mathematically?
b) How do we represent the circles mathematically?
c) How do we check whether the line touches/intersects a given circle?
d) If the line intersects a given circle, what is the arc length which is "created"?

[worker201]

a)
slope = (y2-y1)/(x2-x1);
b = y1 - (slope * x1);

the line's equation is then:
y = b + (slope * x);
or maybe:
y = y1-m(x+x1);
or if you prefer:
y = y1 - (((y2-y1)/(x2-x1)) * (x+x1));

Even though the order of operations covers most of the math, I still use parentheses, for clarity.

So is that enough?  Or do we need to build some kind of array of points that satisfy the equation?

[TheQuirk]

Should be enough.

[worker201]

Should be enough.

You're sooooooo helpful.

Okay,
(b)

how about:
y = q + sqrt(r^2 - (x-p)^2);

where p,q is the center, and r is the radius

[TheQuirk]

Well, what else was I supposed to say? You don't need an array because there are infinitely many possibilities of locations and radii of circles, so you can't just have an array with all the, say, points with integer coordinates and check whether they belong to the circles or not.

Anyway!

y = q + sqrt(r^2 - (x-p)^2);

Almost. That only gives you half a circle. This is what it should be:

y = q +- sqrt(r^2 - (x-p)^2);

[worker201]

c) set the two y= equations above equal and solve?  But what variable do we solve for?  There are 7 unknowns, and that's for only one circle.

[TheQuirk]

What are the other six unknowns?