TopCoder SRM 746 Div1 Hard SpaceProbes

うーん。
https://community.topcoder.com/stat?c=problem_statement&pm=15268

問題

３次元座標において、２つの直線AB・CDと点Eが与えられる。
直線AB上で任意の点P、直線CD上で任意の点Qを取ったとき、PQの中点をRとする。
ER間の距離の最小値を求めよ。

解法

Rの移動範囲を考える。
ACの中点をSとすると、RはSからABの向きとCDの向きが張る平面上を移動できる。
これはP,Qのどちらかを移動すると、Sはその半分だけ移動することから明らかである。
あとはその平面とEとの距離を求めよう。これは外積で平面の法線ベクトルを求め、ベクトルAEとの内積を取ればよい。
ABとCDが平行な場合、Sは直線となるので法線ベクトルを計算できないことに注意。

なお、この問題は数字の桁数が無駄に厳しいので、多倍長の小数が扱える処理系を使う方が確実。

from decimal import *

class SpaceProbes:
	def focusDistance(self, x, y, z):
		getcontext().prec=1000
		x=[Decimal(a) for a in x]
		y=[Decimal(a) for a in y]
		z=[Decimal(a) for a in z]
		
		d1=[x[1]-x[0],y[1]-y[0],z[1]-z[0]]
		d2=[x[3]-x[2],y[3]-y[2],z[3]-z[2]]
		
		cr=(d1[0]*d2[0]+d1[1]*d2[1]+d1[2]*d2[2])**2
		r2=(d1[0]*d1[0]+d1[1]*d1[1]+d1[2]*d1[2])*(d2[0]*d2[0]+d2[1]*d2[1]+d2[2]*d2[2])
		x[0],y[0],z[0]=(x[0]+x[2])/2,(y[0]+y[2])/2,(z[0]+z[2])/2
		
		print(cr,r2)
		if cr==r2:
			# 平行
			r=(d1[0]*d1[0]+d1[1]*d1[1]+d1[2]*d1[2])**Decimal(0.5)
			
			d1[0]/=r
			d1[1]/=r
			d1[2]/=r
			d2=[x[4]-x[0],y[4]-y[0],z[4]-z[0]]
			
			cr=d1[0]*d2[0]+d1[1]*d2[1]+d1[2]*d2[2]
			dx=x[4]-(x[0]+d1[0]*cr)
			dy=y[4]-(y[0]+d1[1]*cr)
			dz=z[4]-(z[0]+d1[2]*cr)
			
			return float((dx*dx+dy*dy+dz*dz)**Decimal(0.5))
		
		
		cross=[d1[1]*d2[2]-d1[2]*d2[1],d1[2]*d2[0]-d1[0]*d2[2],d1[0]*d2[1]-d1[1]*d2[0]]
		r=(cross[0]*cross[0]+cross[1]*cross[1]+cross[2]*cross[2])**Decimal(0.5)
		cross[0]/=r
		cross[1]/=r
		cross[2]/=r
		d2=[x[4]-x[0],y[4]-y[0],z[4]-z[0]]
		cr=cross[0]*d2[0]+cross[1]*d2[1]+cross[2]*d2[2]
		
		return float(abs(cr))

まとめ

Rは線分PQ上を任意に移動できると誤読した…。
まぁ誤読しなくてもC++で突っ込んで精度問題が解決できずSample 2が通らなさそうだけど。