CF250D.Building Bridge

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Two villages are separated by a river that flows from the north to the south. The villagers want to build a bridge across the river to make it easier to move across the villages.

The river banks can be assumed to be vertical straight lines x = a and x = b (0 < a < b).

The west village lies in a steppe at point O = (0, 0). There are n pathways leading from the village to the river, they end at points A__i = (a, y__i). The villagers there are plain and simple, so their pathways are straight segments as well.

The east village has reserved and cunning people. Their village is in the forest on the east bank of the river, but its exact position is not clear. There are m twisted paths leading from this village to the river and ending at points B__i = (b, y'i). The lengths of all these paths are known, the length of the path that leads from the eastern village to point B__i, equals l__i.

The villagers want to choose exactly one point on the left bank of river A__i, exactly one point on the right bank B__j and connect them by a straight-line bridge so as to make the total distance between the villages (the sum of |OA__i| + |A__i__B__j| + l__j, where |XY| is the Euclidean distance between points X and Y) were minimum. The Euclidean distance between points (_x_1, _y_1) and (_x_2, _y_2) equals .

Help them and find the required pair of points.

两条村庄被一条由北向南流动的河流隔开。村民们希望在河上修建一座桥梁,以便于在两村之间通行。

河岸可视为两条竖直的直线:x=ax = a 和 x=bx = b(其中 0<a<b0 < a < b)。

西边的村庄位于草原上的点 O=(0,0)O = (0, 0)。从该村庄通往河流共有 nn 条路径,它们均为直线段,终点分别位于左岸上的点 Ai=(a,yi)A_i = (a, y_i)。

东边的村庄则居住在河东岸的森林中,其居民性格含蓄而精明,因此村庄的确切位置尚不明确。从该村庄通往河流共有 mm 条蜿蜒曲折的小路,它们的终点分别位于右岸上的点 Bi=(b,yi′)B_i = (b, y'_i)。所有这些小路的长度均已知:从东边村庄到点 BiB_i 的小路长度为 lil_i。

村民们希望恰好选择左岸上的一个点 AiA_i、右岸上的一个点 BjB_j,并用一条直线桥梁连接它们,使得两村庄之间的总通行距离(即 ∣OAi∣+∣AiBj∣+lj|OA_i| + |A_iB_j| + l_j,其中 ∣XY∣|XY| 表示点 XX 与 YY 之间的欧几里得距离)最小。点 (x1,y1)(x_1, y_1) 与 (x2,y2)(x_2, y_2) 之间的欧几里得距离为 。

请帮助他们找出满足要求的点对 (Ai,Bj)(A_i, B_j)。

输入格式

The first line contains integers n, m, a, b (1 ≤ n, m ≤ 105, 0 < a < b < 106).

The second line contains n integers in the ascending order: the i-th integer determines the coordinate of point A__i and equals y__i (|y__i| ≤ 106).

The third line contains m integers in the ascending order: the i-th integer determines the coordinate of point B__i and equals y'i (|y'i| ≤ 106).

The fourth line contains m more integers: the i-th of them determines the length of the path that connects the eastern village and point B__i, and equals l__i (1 ≤ l__i ≤ 106).

It is guaranteed, that there is such a point C with abscissa at least b, that |B__i__C| ≤ l__i for all i (1 ≤ i ≤ m). It is guaranteed that no two points A__i coincide. It is guaranteed that no two points B__i coincide.

第一行包含四个整数 nn、mm、aa、bb(1≤n,m≤1051 \leq n, m \leq 10^5,0<a<b<1060 < a < b < 10^6)。

第二行包含 nn 个升序排列的整数:第 ii 个整数表示点 AiA_i 的纵坐标,记为 yiy_i(∣yi∣≤106|y_i| \leq 10^6)。

第三行包含 mm 个升序排列的整数:第 ii 个整数表示点 BiB_i 的纵坐标,记为 yi′y'_i(∣yi′∣≤106|y'_i| \leq 10^6)。

第四行包含 mm 个整数:其中第 ii 个整数表示连接东村与点 BiB_i 的路径长度,记为 lil_i(1≤li≤1061 \leq l_i \leq 10^6)。

保证存在一个横坐标至少为 bb 的点 CC,使得对所有 ii(1≤i≤m1 \leq i \leq m)均有 ∣BiC∣≤li|B_i C| \leq l_i。
保证任意两个点 AiA_i 均不重合。
保证任意两个点 BiB_i 均不重合。

输出格式

Print two integers — the numbers of points on the left (west) and right (east) banks, respectively, between which you need to build a bridge. You can assume that the points on the west bank are numbered from 1 to n, in the order in which they are given in the input. Similarly, the points on the east bank are numbered from 1 to m in the order in which they are given in the input.

If there are multiple solutions, print any of them. 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.

输出两个整数——分别表示需要建桥的西岸(左岸)和东岸(右岸)上的点的编号。你可以假设西岸上的点按输入中给出的顺序编号为 11 到 nn;类似地,东岸上的点按输入中给出的顺序编号为 11 到 mm。

若存在多个解,输出任意一个即可。只要最终路径长度与裁判组答案的绝对误差或相对误差均不超过 10−610^{-6},该解即被视为正确。

输入输出样例

  • 输入#1

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

    输出#1

    2 2

输入解题思路,AI测评打分。不知道怎么写?

首页