2018-2019 ACM-ICPC, Asia East Continent Finals

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 s s to the position of the star t t t, while a sphere — the earth staying there as an obstacle. They are in a 3-dimensional Euclidean space. s s s and t t t may be at the same position.

Input:

The first line contains an integer T <mtext>   </mtext> ( 1 T 1000 ) T~(1 \leq T \leq 1000) T (1T1000), the number of test cases. Then T T T test cases follow.
Each test case contains two lines.
The first line contains four integers o x , o y , o z , r o_x, o_y, o_z, r ox,oy,oz,r, the positions in each dimension of the center of the sphere o o o and its radius.
The second line contains six integers s x , s y , s z , t x , t y , t z s_x, s_y, s_z, t_x, t_y, t_z sx,sy,sz,tx,ty,tz, the positions in each dimension of the starting point s s s and the terminal point t t t, respectively. Notice that s s s and t t t may be at the same position.
It is guaranteed that neither s s s nor t t t is strictly inside the obstacle, and each value of a position or a radius in the input belongs to [ 1 , 1000 ] [1, 1000] [1,1000].

Output:

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

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;
}
全部评论

相关推荐

03-15 00:45
已编辑
高德地图_go开发(实习员工)
问的很简单都秒了,但是面试官没开摄像头,疑似kpi,无后续。--------------------3/14更新,3/12通知给了口头offer,3/13发了意向书,已拒。一面(35min)(25/3/6)(无后续)&nbsp;&nbsp;&nbsp;&nbsp;1、自我介绍&nbsp;&nbsp;&nbsp;&nbsp;2、介绍一下你的那个Python相关项目(本科毕设,web系统+算法模型提供部分接口)&nbsp;&nbsp;&nbsp;&nbsp;3、Java面向对象有哪些特点呢?详细说一下。&nbsp;&nbsp;&nbsp;&nbsp;4、介绍一下hashmap;为什么要把链表转换为红黑树呢?红黑树查找的时间复杂度?1.7和1.8的区别。&nbsp;&nbsp;&nbsp;&nbsp;5、介绍一下concurrentHashmap。&nbsp;&nbsp;&nbsp;&nbsp;6、synchronized锁和Lock锁有什么区别?&nbsp;&nbsp;&nbsp;&nbsp;7、公平锁的一个底层是怎么实现的呢?&nbsp;&nbsp;&nbsp;&nbsp;8、线程池的核心参数、拒绝策略、提交一个任务执行流程?&nbsp;&nbsp;&nbsp;&nbsp;9、spring有哪些特点?(ioc/aop)&nbsp;&nbsp;&nbsp;&nbsp;10、spring中对于循环依赖是怎么解决的?&nbsp;&nbsp;&nbsp;&nbsp;11、MySQL和redis的区别?&nbsp;&nbsp;&nbsp;&nbsp;12、MySQL的索引结构是什么?&nbsp;&nbsp;&nbsp;&nbsp;13、MySQL的事务有哪些特性?怎么保证?&nbsp;&nbsp;&nbsp;&nbsp;14、MySQL的默认隔离级别?可重复读是怎么做到的呢?&nbsp;&nbsp;&nbsp;&nbsp;15、介绍一下MVCC和快照读readview。&nbsp;&nbsp;&nbsp;&nbsp;16、一般在什么场景下会使用redis?&nbsp;&nbsp;&nbsp;&nbsp;17、对于大量的请求,如果此时缓存中还没有写入数据怎么办?&nbsp;&nbsp;&nbsp;&nbsp;18、介绍一下redis实现的分布式锁。&nbsp;&nbsp;&nbsp;&nbsp;19、有用过es和mongo&nbsp;DB吗?(知道,没用过)&nbsp;&nbsp;&nbsp;&nbsp;20、消息中间件用过吗?说一下你的使用场景?&nbsp;&nbsp;&nbsp;&nbsp;21、一个场景,如果说有一个接口响应的比较慢,如果说让你排查,你会怎么去排查?(上下游接口、大key问题,只答了两,后面试官补充)&nbsp;&nbsp;&nbsp;&nbsp;无手撕,反问业务。
胖墩墩的查理在学c语言:哥们我是五号面的 流程差不多
查看21道真题和解析
点赞 评论 收藏
分享
03-18 17:22
门头沟学院 Java
代码飞升:海投就完了,别管评论区那个sbb卖课的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务