← 返回题目列表

Codeforces · 250/D

D. 建筑桥梁

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

两个村庄被一条从北向南流淌的河流隔开。村民们想在河上建一座桥,以便更方便地穿过村庄。

河岸可以假设为垂直直线 x = a 和 x = b (0 < a < b)。

西村位于草原上,点 O = (0, 0)。从村庄到河流有 n 条路径,它们的终点为点 Ai = (a, yi)。那里的村民朴实无华,所以他们的道路也是笔直的。

东村人矜持狡猾。他们的村庄在河东岸的森林里,但具体位置并不清楚。从这个村庄到河边有 m 条蜿蜒的小路,终点为 Bi = (b, y'i)。所有这些路径的长度都是已知的,从东边村庄到Bi点的路径长度等于li。

村民希望在Ai河左岸恰好选择一个点,在右岸Bj恰好选择一个点,并通过直线桥将它们连接起来,以使村庄之间的总距离(|OAi| + |AiBj| + lj之和,其中|XY|为X点和Y点之间的欧氏距离)最小。点 (x1, y1) 和 (x2, y2) 之间的欧几里德距离等于 $$\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$$。

帮助他们找到所需的点对。

输入

第一行包含整数 n、m、a、b (1 ≤ n, m ≤ 105, 0 < a < b < 106)。

第二行包含 n 个整数,按升序排列:第 i 个整数确定点 Ai 的坐标,等于 yi (|yi| ≤ 106)。

第三行包含 m 个整数,按升序排列:第 i 个整数确定 Bi 点的坐标,等于 y'i (|y'i| ≤ 106)。

第四行又包含 m 个整数:其中第 i 个整数决定了连接东部村庄和 Bi 点的路径长度,等于 li (1 ≤ li ≤ 106)。

保证存在这样一个点C,其横坐标至少为b,即|BiC|对于所有 i (1 ≤ i ≤ m),≤ li。保证没有两点 Ai 重合。保证没有两点Bi重合。

输出

Print two integers — the numbers of points on the left (west) and right (east) banks, respectively, between which you need to build a bridge.您可以假设西岸的点按照输入中给出的顺序从 1 到 n 编号。同样,东岸的点按照输入中给出的顺序从 1 到 m 编号。

如果有多个解决方案,请打印其中任何一个。 The solution will be accepted if the final length of the path will differ from the answer of the jury by no more than 10 - 6 in absolute or relative value.

示例

输入 #1

3 2 3 5
-2 -1 4
-1 2
7 3

输出 #1

2 2