UVa 10180

UVA_10180.cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

static const double eps = 1e-8;

int cmp(double x)
{
    if (fabs(x) < eps) return 0;
    if (x > 0) return 1;
    return -1;
}

double sqr(double x)
{
    return x * x;
}

double hypot(double a, double b)
{
    return sqrt(sqr(a) + sqr(b));
}

double tribe(double a, double b)
{
    return sqrt(sqr(a) - sqr(b));
}

struct Point {
    double x, y;
    Point(double a = 0.0, double b = 0.0): x(a), y(b) {}
    double distance(const Point &rhs) const
    {
       return sqrt(sqr(rhs.x - x) + sqr(rhs.y - y));
    }
    Point operator+(const Point &rhs) const
    {
        return Point(x + rhs.x, y + rhs.y);
    }
    Point operator-(const Point &rhs) const
    {
        return Point(x - rhs.x, y - rhs.y);
    }
    double operator*(const Point &rhs) const
    {
        return x * rhs.x + y * rhs.y;
    }
};

class Solver {
public:
    Solver(void);
    void run(void);
private:
    double cross(const Point &O, const Point &A, const Point &B)
    {
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
    }
    double distance(const Point &p1, const Point &p2)
    {
        return hypot(p1.x - p2.x, p1.y - p2.y);
    }
    bool intersectWithCircle(void)
    {
        double a = B.distance(O);
        double b = A.distance(O);
        double c = A.distance(B);

        if (cmp(a) <= 0 || cmp(b) <= 0 || cmp(c) <= 0)
            return false;

        if (sqr(a) >= sqr(b) + sqr(c))
            return cmp(b - radius) < 0;
        if (sqr(b) >= sqr(a) + sqr(c))
            return cmp(a - radius) < 0;

        double l = (a + b + c) / 2;
        double s = sqrt(l * (l-a) * (l-b) * (l-c));
        return cmp(2 * s / c - radius) < 0;
    }

    Point A, B, O;
    double length, radius;
};

Solver::Solver()
{
    scanf("%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &radius);

    length = A.distance(B);
}

void Solver::run()
{
    if (!intersectWithCircle()) {
        printf("%.3lf\n", length + eps);
    } else {
        double d1 = O.distance(A);
        double d2 = O.distance(B);
        double d = tribe(d1, radius) + tribe(d2, radius);

        double t = acos((sqr(d1) + sqr(d2) - sqr(length)) / (2 * d1 * d2)) -
                   acos(radius / d1) - acos(radius / d2);
        d += t * radius;
        printf("%.3lf\n", d + eps);
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        Solver s;
        s.run();
    }

    return 0;
}