狐狸二郎居住的森林里住着一个鬼魂。 鬼魂喜欢恶作剧,总是用恶作剧给二郎和他的动物朋友们带来惊喜。 然而,鬼恶作剧只是有趣的恶作剧,不会让动物感到不舒服。 而且,与森林外的鬼魂不同,这个鬼魂不会变成可怕的人。 这就是为什么二郎和其他动物喜欢这个友好的鬼魂。
有一天,二郎和他的朋友们为鬼举办了一场生日聚会。 二郎和他的朋友们准备的生日蛋糕显示了鬼魂的年龄。 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。
例
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
小課題 2 (40 点)
- 1≤N≤100000
- 0≤i<N,Cz[i]=0,Tz[i]=0。
小課題 3 (41 点)
- 1≤N≤100000
实施细节
制限
- 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 坐标。