LOJ 1433 - Minimum Arc Distance

Tags : euclidean geometry, tri-gonometry

We will be given the cordinates of a circle's center and two points on the circumference. We have find out the arc length those two points produce.

Solution

To solve it, we first must remember the formula to calculate the arc length between 2 points of a circle, which is

arc length = (radius of the circle) * (angle created by the 2 points at the center of the circle, in radian)

To understand this formula in a quick look or to refresh our memories, we can see that the arc length is proportional to the θ,angle created at the center of a circle. The bigger the arc length, the bigger becomes the angle in between the 2 points of the cirlce and vice versa. We can see that the Circumference is the longest arc length of a circle, also we know C = 2 * π * (radius of the cirlce).

C is the arc length when θ = 2 * π
1 is the arc length when θ = (2 * π)/C
                           = (2 * π)/(2 * π *r)
                           = 1/r
S is the arc length when θ = S/r

So, S = θ * r

We can calculate the radius of the circle simply by taking the distance of any point of a circle to its center, distance = √((P1_x - P2_x)² + (P1_y - P2_y)²).

Now to calculate the angle we can use the cosine rule of triangles,

AB (Straight line, not the arc length) = √(OA²+OB²-2*OA*OB*cosθ)  
=> AB²  = OA²+OB²-2*OA*OB*cosθ
=> cosθ = (OA²+OB²-AB²)/2*OA*OB
=> θ = arccos ((OA²+OB²-AB²)/2*OA*OB)

We again use the distance formula for each line and now we have the necessary values that we can plug into the arc length formula.

The above implementation is accepted.

Solution in C

#include <stdio.h>
#include <math.h>

int main()
{
    int testCases, ox, oy, ax, ay, bx, by;
    scanf("%d", &testCases);
    double OA, OB, AB, angle;
    for (int i = 1; i <= testCases; i++)
    {
        scanf("%d %d %d %d %d %d", &ox, &oy, &ax, &ay, &bx, &by);

        OA = sqrt(pow(ax - ox, 2) + pow(ay - oy, 2));
        OB = sqrt(pow(bx - ox, 2) + pow(by - oy, 2));
        AB = sqrt(pow(ax - bx, 2) + pow(ay - by, 2));

        angle = acos((pow(OA, 2) + pow(OB, 2) - pow(AB, 2)) / (2 * OA * OB));

        printf("Case %d: %.3lf\n", i, OA * angle);
    }
    return 0;
}

Tutorial source