Interstellar … Fantasy 一个不很难的计算几何

Interstellar … Fantasy 一个不很难的计算几何

题意：

给你一个球，球的坐标：ox,oy,oz 和球的半径：r

再给你两个三维坐标，要求这两个点不能穿过球，问两点之间最短的距离是多少。

题解：

高中数学题，不是很难，注意利用角度的关系，还有余弦定理

首先要判断一下两点的连线是否穿过球，如果穿过球，那么就是两点对球做切线，点到切点的距离加上一段圆弧的长度。

怎么判断是否穿过球呢，如果ost和ots都是锐角并且圆心到直线的距离小于r才可以判断穿过球心，这两个条件缺一不可！！！

今天的CCF出了一个差不多的题目。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1);
typedef long long ll;
ll dis(int x1,int y1,int z1,int x2,int y2,int z2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll ox,oy,oz,r;
		scanf("%lld%lld%lld%lld",&ox,&oy,&oz,&r);
		ll sx,sy,sz,tx,ty,tz;
		scanf("%lld%lld%lld%lld%lld%lld",&sx,&sy,&sz,&tx,&ty,&tz);
		double SO = sqrt(1.0*dis(sx,sy,sz,ox,oy,oz));
		double TO = sqrt(1.0*dis(tx,ty,tz,ox,oy,oz));
		double ST = sqrt(1.0*dis(sx,sy,sz,tx,ty,tz));
		double deltS = acos(1.0*r/SO);
		double deltT = acos(1.0*r/TO);
		double delt = acos((SO*SO+TO*TO-ST*ST)/(2*SO*TO))-deltT-deltS;
		double Tx = acos((ST*ST+TO*TO-SO*SO)/(2*ST*TO));
		double Sx = acos((ST*ST+SO*SO-TO*TO)/(2*ST*SO));
		double h = TO*sin(Tx),ans = 0;
		if(Sx<PI/2&&Tx<PI/2&&h<r) ans = sqrt(SO*SO-r*r)+sqrt(TO*TO-r*r)+delt*r;
		else ans = ST;
		// cout<<ans<<endl;
		printf("%.8f
",ans);
	}
}