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

実行時間制限: 0 msec / メモリ制限: 256 MB

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

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

課題

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

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

  • 次のパラメータを持つプロシージャ 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])を点Tiとすると、Ti0≤i<Nについて集めた集合{Ti}Si0≤i<Nについて集めた集合{Si}は等しい。(注意:Si=Tiとは限らない事に注意せよ。)
    このプロシージャはおばけの居る座標(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)を考えると、
C1の影S1T2
C2の影S2T3
C3の影S3T1
であることが分かるので、このGがおばけのいる場所である。
よってFindGhostanswer(0.3,0.4,0.5)を呼び出す。

小課題

小課題 1 (19 点)

  • 1≤N≤10
この小課題のテストケースではすべてのCiが同一平面上にあるということはない。

小課題 2 (40 点)

  • 1≤N≤100000
  • 0≤i<Nについて、Cz[i]=0,Tz[i]=0である。
この小課題のテストケースでは、すべてのCiが同一直線上にあるということはない。

小課題 3 (41 点)

  • 1≤N≤100000
この小課題のテストケースでは、すべてのCiが同一平面上にあるということはない。

実装の詳細

制限

  • CPU 時間制限: 1秒
  • メモリ制限: 256 MB
    注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。

インターフェース (API)

  • 実装フォルダ: ghost/ (プロトタイプ: ghost.zip)
  • 競技者が実装するファイル: ghost.cpp
  • 提出ファイルのインターフェース: ghost.h
  • 採点プログラムのサンプル: grader.cpp
  • 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
    注意:採点プログラムのサンプルは次の書式の入力を読み込む。
    • 1 行目: 整数Nが書かれている。Nはろうそくの数を表す。
    • 2 行目から 1+N 行目: 1 ≤ i ≤ N に対し、i+1行目には実数Cx,Cy,Czが書かれている。これらはそれぞれろうそくCiのx,y,z座標を表す。
    • 2+N 行目から 1+2N 行目: 1 ≤ i ≤ N に対し、i+N+1行目には実数Ty,Tzが書かれている。これらはそれぞれ影Tiのy,z座標を表す。
  • 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
    注意:採点プログラムのサンプルは次の書式の出力を書き出す。
    • 1行目:実数Gx,Gy,Gzが書かれている。これらはそれぞれおばけのいる地点Gのx,y,z座標を表す。