F. Interstellar … Fantasy

Description:

Unfortunately, the boy finally got bankrupt. Looking at his receding figure, Rikka understood more about the world — but she is still herself. Though, she still sat on the tower and spent time with the low gravity, feeling lost.
She looked at the deep dark sky, where the blue round Earth is shining overhead. Rikka thought about her families, her friends, and her homeland. Is she in her dream or a “real” world? The girl of chunibyo felt afraid for the first time since the journey began.
She saw a bright star traveling fast around the earth — maybe a geostationary space station. How could she get there? Daydream started again.
In other words, Rikka wonders the minimum distance she needs to travel from her position $s$ to the position of the star $t$ , while a sphere — the earth staying there as an obstacle. They are in a 3-dimensional Euclidean space. $s$ and $t$ may be at the same position.

Input:

The first line contains an integer $T <mtext> </mtext> (1 \leq T \leq 1000)$ , the number of test cases. Then $T$ test cases follow.
Each test case contains two lines.
The first line contains four integers $o_{x}, o_{y}, o_{z}, r$ , the positions in each dimension of the center of the sphere $o$ and its radius.
The second line contains six integers $s_{x}, s_{y}, s_{z}, t_{x}, t_{y}, t_{z}$ , the positions in each dimension of the starting point $s$ and the terminal point $t$ , respectively. Notice that $s$ and $t$ may be at the same position.
It is guaranteed that neither $s$ nor $t$ is strictly inside the obstacle, and each value of a position or a radius in the input belongs to $[1, 1000]$ .

Output:

Output one number, the minimum distance from $s$ to $t$ without entering the sphere obstacle. Your answer is considered correct if the absolute or relative error doesn’t exceed $1 0^{- 6}$ .

Sample Input:

2
2 1 1 1
1 1 1 3 1 1
2 1 1 1
1 2 2 3 1 1

Sample Output:

3.14159265
2.64517298

题目链接

空间内有两点（S、T）一球（球心O，半径R），求两点不经过球内的最短路径。

显然最短路径在面OST上。

若两点线段与球无交点则答案为两点距离。

若两点线段与球有交点则最短路径需绕过球面，显然最短路径为两点做球的切线与两切点在球上弧长之和，这就可以转换为平面问题。

此题精度卡的比较严。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8;

int Sgn(double Key) {
    if (fabs(Key) < eps) {
        return 0;
    }
    return Key < 0 ? -1 : 1;
}

struct Point {
    double X, Y, Z;
};

typedef Point Vector;

Vector operator - (Vector Key1, Vector Key2) {
    return (Vector){Key1.X - Key2.X,
                    Key1.Y - Key2.Y,
                    Key1.Z - Key2.Z};
}

double operator * (Point Key1, Point Key2) {
    return Key1.X * Key2.X + Key1.Y * Key2.Y + Key1.Z * Key2.Z;
}

double Length(Vector Key) {
    return sqrt(Key * Key);
}

double operator ^ (Vector Key1, Vector Key2) {
    return Length((Vector){Key1.Y * Key2.Z - Key1.Z * Key2.Y,
                           Key1.Z * Key2.X - Key1.X * Key2.Z,
                           Key1.X * Key2.Y - Key1.Y * Key2.X});
}

double DisPointToPoint(Point Key1, Point Key2) {
    return sqrt((Key1 - Key2) * (Key1 - Key2));
}

double GetAngle(Vector Key1, Vector Key2) {
    return fabs(atan2(fabs(Key1 ^ Key2), Key1 * Key2));
}

struct Line {
    Point S, T;
};

typedef Line Segment;

double Length(Segment Key) {
    return DisPointToPoint(Key.S, Key.T);
}

double DisPointToLine(Point Key1, Line Key2) {
    return fabs((Key1 - Key2.S) ^ (Key2.T - Key2.S)) / Length(Key2);
}

double DisPointToSegment(Point Key1, Segment Key2) {
    if (Sgn((Key1 - Key2.S) * (Key2.T - Key2.S)) < 0 ||
        Sgn((Key1 - Key2.T) * (Key2.S - Key2.T)) < 0) {
        return min(DisPointToPoint(Key1, Key2.S), DisPointToPoint(Key1, Key2.T));
    }
    return DisPointToLine(Key1, Key2);
}

struct Sphere {
    Point Center;
    double Radius;
};

int T;
Sphere Obstacle;
Point Start, End;
double DisOS, DisOE;
double Angle;
double Ans;

int main(int argc, char *argv[]) {
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%lf%lf%lf%lf", &Obstacle.Center.X, &Obstacle.Center.Y, &Obstacle.Center.Z, &Obstacle.Radius);
        scanf("%lf%lf%lf", &Start.X, &Start.Y, &Start.Z);
        scanf("%lf%lf%lf", &End.X, &End.Y, &End.Z);
        Ans = 0.0;
        if (Sgn(DisPointToSegment(Obstacle.Center, (Segment){Start, End}) - Obstacle.Radius) >= 0) {
            printf("%.8lf\n", DisPointToPoint(Start, End));
            continue;
        }
        DisOS = DisPointToPoint(Obstacle.Center, Start);
        DisOE = DisPointToPoint(Obstacle.Center, End);
        Angle = GetAngle(Start - Obstacle.Center, End - Obstacle.Center) -
                acos(Obstacle.Radius / DisOS) -
                acos(Obstacle.Radius / DisOE);
        Ans += sqrt(DisOS * DisOS - Obstacle.Radius * Obstacle.Radius);
        Ans += sqrt(DisOE * DisOE - Obstacle.Radius * Obstacle.Radius);
        Ans += Angle * Obstacle.Radius;
        printf("%.8lf\n", Ans);
    }
    return 0;
}

2018-2019 ACM-ICPC, Asia East Continent Finals