← 返回题目列表

AtCoder · ijpc_ghost

B. 鬼魂生日会

中文机器翻译题面 查看原题

狐狸二郎居住的森林里住着一个鬼魂。 鬼魂喜欢恶作剧,总是用恶作剧给二郎和他的动物朋友们带来惊喜。 然而,鬼恶作剧只是有趣的恶作剧,不会让动物感到不舒服。 而且,与森林外的鬼魂不同,这个鬼魂不会变成可怕的人。 这就是为什么二郎和其他动物喜欢这个友好的鬼魂。

有一天,二郎和他的朋友们为鬼举办了一场生日聚会。 二郎和他的朋友们准备的生日蛋糕显示了鬼魂的年龄。 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,G和Ci的直线与墙壁的交点处投射出阴影。Si(0,Syi,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。
    该过程仅调用一次。 (0,Ty[i],Tz[i])收集了关于Ti可以表示为Ti的0≤i<N 对于的一组{Ti}和Si的0≤i<N 对于的一组{Si}相等。 (注:Si=T 请注意,i不一定是这种情况。) 这个程序就是鬼魂的坐标。(Gx,Gy,Gz) 计算并答案(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的影子S1是T2、 C2的影子S2是T3、 C3的影子S3是T1 ,所以这个G是鬼魂所在的地方。 因此FindGhost表示答案(0.3,0.4,0.5) 致电。

小課題

小課題 1 (19 点)

  • 1≤N≤10
在此子任务测试用例中,所有Ci从未在同一平面上。

小課題 2 (40 点)

  • 1≤N≤100000
  • 0≤i&ltN,Cz[i]=0,Tz[i]=0。
在此子任务测试用例中,所有Ci永远不会在同一条直线上。

小課題 3 (41 点)

  • 1≤N≤100000
在此子任务测试用例中,所有Ci从未在同一平面上。

实施细节

制限

  • CPU时间限制:1秒
  • 内存限制:256 MB
    注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。

接口 (API)

  • 实现文件夹: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 坐标。