OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题1652--激光

1652: 激光

时间限制: 1 Sec  内存限制: 128 MB
提交: 40  解决: 20
[提交] [状态] [讨论版] [命题人:]

题目描述

在一个从(0,0)到(x,y)的二维坐标平面上,初始你位于(0,0)位置,想要前往(x,y)。然而,在水平方向上有n个激光发射器,其中第 i 个激光发射器发射的激光连续跨越(0,ai)至(x,ai);在竖直方向上有m个激光发射器,其中第 i 个激光发射器发射的激光连续跨越(bi,0)至(bi,y)。
你可以想任意方向移动到达(x,y),但是你的移动必须是位于平面内的连续曲线,每次穿过水平或竖直的激光时都算一次穿越,当穿过两条激光的交点则算作两次穿越。你需要计算从(0,0)到达(x,y)所需要的最少穿越次数。
例如,如果 x=y=2,n=m=1,a=[1],b=[1],移动过程如下:



输入

第一行中输入四个整数n,m,x,y;(1 <= n,m <= 2e5)
接下来的一行输入n个整数,表示水平激光的yi坐标;(1 <= yi <= 1e9)
第三行输入m个整数,表示垂直激光的xi坐标。(1 <= xi <= 1e9)

输出

输出达到 (x,y) 所需的最小穿越次数。

样例输入 Copy

1 1 2 2
1
1

样例输出 Copy

2

来源/分类