やさしいおばけ の たんじょうびかい (Friendly Ghost's Birthday Party)

きつねの次郎のすむ森には一匹のおばけが住んでいます。
お化けはいたずらが大好きで、いつも次郎やその仲間のどうぶつたちをいたずらで驚かせて楽しんでいます。
ですが、おばけのいたずらは楽しいいたずらで、どうぶつたちをいやがらせることはありません。
また、森の外のおばけとは違い、このおばけは怖い人間に化けたりもしません。
なので、次郎たちどうぶつはこのやさしいおばけが大好きです。

ある日、次郎たちはおばけの誕生日会を開きました。
次郎たちの用意したバースデーケーキには、おばけの年齢である N 本の火が灯ったろうそくが立っています。
しかし、招待されたおばけはまた楽しいいたずらを思いつき、次郎たちを驚かせようと透明に化けてしまいました。
次郎たちは今日の主役であるおばけが見えなくなって困ってしまったのですが、とある事に気がつきました。
おばけは透明になって見えないのに、ろうそくの光でおばけの影が壁に映っているのです！
次郎たちは、この影によっておばけがどこに居るのか分からないだろうかと考えました。
バースデーケーキはとても大きいので、おばけ、ろうそく、おばけの影は点と考える事ができます。

xyz空間中に、1匹のおばけとN個のろうそくがある。
おばけは地点G(Gx,Gy,Gz)に居て、
i番目のろうそくの火は地点C_i(Cx[i],Cy[i],Cz[i])に灯っている。
また、各iについて、0<Gx<Cx[i]が満たされている。
yz平面(x=0で表される平面)には壁があり、各iについて、GとC_iを結んだ直線と壁の交点に影S_i(0,S_yi,S_zi)が映っている。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ FindGhost(N,Cx,Cy,Cz,Ty,Tz):
  • N -- ろうそくの本数。
  • Cx -- ろうそくの火のx座標を表す実数の配列。0≤i<Nに対して0≤Cx[i]≤1を仮定してよい。
  • Cy -- ろうそくの火のy座標を表す実数の配列。0≤i<Nに対して0≤Cy[i]≤1を仮定してよい。
  • Cz -- ろうそくの火のz座標を表す実数の配列。0≤i<Nに対して0≤Cz[i]≤1を仮定してよい。
  • Ty -- 影のy座標を表す実数の配列。0≤i<Nに対して0≤Ty[i]≤1を仮定してよい。
  • Tz -- 影のz座標を表す実数の配列。0≤i<Nに対して0≤Tz[i]≤1を仮定してよい。
  このプロシージャは1回だけ呼び出される。
  (0,Ty[i],Tz[i])を点T_iとすると、T_iを0≤i<Nについて集めた集合{T_i}とS_iを0≤i<Nについて集めた集合{S_i}は等しい。(注意:S_i=T_iとは限らない事に注意せよ。)
  このプロシージャはおばけの居る座標(Gx,Gy,Gz)を計算し、answer(Gx,Gy,Gz)を呼び出す。このとき、正しいおばけの位置と(Gx,Gy,Gz)の距離が10^-5以下であったとき正答とみなされる。

N=3
Cx={0.9,0.45,0.6}
Cy={0.8,0.2,0.1}
Cz={0.5,0.4,0.8}
Ty={0.7,0.2,0.8}
Tz={0.2,0.5,0.7}
の場合を考える。

このとき各点は下図の位置にある。

G(0.3,0.4,0.5)を考えると、
C₁の影S₁がT₂、
C₂の影S₂がT₃、
C₃の影S₃がT₁
であることが分かるので、このGがおばけのいる場所である。
よってFindGhostはanswer(0.3,0.4,0.5)を呼び出す。