Mice

题意翻译

#### 题目描述： 在平面上给出两条直线 $y = Y_0$ 和 $y = Y_1$。在 $y = Y_0$ 上有 $n$ 只老鼠，第 $i$ 只老鼠横坐标为 $x_{1, i}$，在 $y = Y_1$ 上有 $m$ 个奶酪，第 $i$ 个奶酪横坐标为 $x_{2, i}$。已知一只老鼠的捕食策略如下： $1.$ 如果离这只老鼠最近的奶酪有且只有一个，那么这只老鼠会往这个奶酪移动。 $2.$ 如果有多个奶酪离老鼠距离最近，那么这只老鼠会选择向使所有老鼠中挨饿个数最少的奶酪移动。 每只老鼠的移动速度都是一样的，当某些老鼠到达某个奶酪并且当前奶酪还没有被吃掉时，他们会吃掉奶酪并且不再挨饿。如果某个老鼠在到达奶酪时奶酪已经被吃掉了，那么它不会再进行移动，此时我们认为它处于挨饿状态。 请输出最终处于挨饿状态的老鼠个数。 #### 输入格式： 第一行包括 $4$ 个整数 $n, m, Y_0, Y_1$（$1 \le n \le 10^5, 0 \le m \le 10^5, 0 \le Y_0 \le 10^7, 0 \le Y_1 \le 10^7, Y_0 \ne Y_1$）。 第二行包括 $n$ 个整数 $x_{1, i}$（$|x_{1, i}| \le 10^7$）。 第三行包括 $m$ 个整数 $x_{2, i}$（$|x_{2, i}| \le 10^7$）。 #### 输出格式： 输出一行一个整数，代表最终处于挨饿状态的老鼠个数。

题目描述

Modern researches has shown that a flock of hungry mice searching for a piece of cheese acts as follows: if there are several pieces of cheese then each mouse chooses the closest one. After that all mice start moving towards the chosen piece of cheese. When a mouse or several mice achieve the destination point and there is still a piece of cheese in it, they eat it and become well-fed. Each mice that reaches this point after that remains hungry. Moving speeds of all mice are equal. If there are several ways to choose closest pieces then mice will choose it in a way that would minimize the number of hungry mice. To check this theory scientists decided to conduct an experiment. They located $ N $ mice and $ M $ pieces of cheese on a cartesian plane where all mice are located on the line $ y=Y_{0} $ and all pieces of cheese — on another line $ y=Y_{1} $ . To check the results of the experiment the scientists need a program which simulates the behavior of a flock of hungry mice. Write a program that computes the minimal number of mice which will remain hungry, i.e. without cheese.

输入输出格式

输入格式

The first line of the input contains four integer numbers $ N $ ( $ 1<=N<=10^{5} $ ), $ M $ ( $ 0<=M<=10^{5} $ ), $ Y_{0} $ ( $ 0<=Y_{0}<=10^{7} $ ), $ Y_{1} $ ( $ 0<=Y_{1}<=10^{7} $ , $ Y_{0}≠Y_{1} $ ). The second line contains a strictly increasing sequence of $ N $ numbers — $ x $ coordinates of mice. Third line contains a strictly increasing sequence of $ M $ numbers — $ x $ coordinates of cheese. All coordinates are integers and do not exceed $ 10^{7} $ by absolute value.

输出格式

The only line of output should contain one number — the minimal number of mice which will remain without cheese.

输入输出样例

输入样例 #1

3 2 0 2
0 1 3
2 5

输出样例 #1

1

说明

All the three mice will choose the first piece of cheese. Second and third mice will eat this piece. The first one will remain hungry, because it was running towards the same piece, but it was late. The second piece of cheese will remain uneaten.