Задача №114924. Морской бой
В старом игровом автомате «Морской бой» игрок сбивает торпедами корабли, двигающиеся по игровому полю слева направо или справа налево.
В нашем варианте игры на поле может находиться одновременно несколько кораблей. Все корабли движутся с одинаковыми скоростями налево или направо. За одну секунду каждый корабль передвигается на единицу длины системы координат. Это означает, что через одну секунду после начала игры корабль, который находился в точке 20 и двигался направо, будет находиться в точке 21, а корабль, который находился в точке 30 и двигался налево, окажется в точке 29.
Вы можете выпускать торпеды, которые будут подбивать корабли. Торпеда, выпущенная в точке с какой-то координатой, уничтожает корабль, находящийся в этот момент в этой точке. При этом если в этой точке в этот момент времени окажется несколько кораблей, то торпеда подобьёт все эти корабли. Вы даже можете одновременно выпускать несколько торпед!
Подбейте все корабли, используя минимальное число торпед.
В первой строке содержится целое число \(N\) — количество кораблей, движущихся влево (с уменьшением координаты). Во второй строке содержится целое число \(M\) — количество кораблей, движущихся вправо (с увеличением координаты). Гарантируется, что \(1 \leq N + M \leq 10^5\), \(N\geq 0\) и \(M\geq 0\).
Следующие \(N\) строк содержат по одному целому числу \(l_i\) — начальные координаты кораблей, двигающихся влево. Следующие \(M\) строк содержат по одному целому числу \(r_i\) — начальные координаты кораблей, двигающихся вправо. Координаты \(l_i\) идут в порядке возрастания, координаты \(r_i\) также заданы в порядке возрастания. Гарантируется, что все начальные координаты \(l_i\) и \(r_i\) чётные, различные и не превосходят по модулю \(10^9\).
Программа должна вывести столько строк, сколько торпед необходимо для уничтожения всех кораблей, при этом \(i\)-я строка должна содержать два целых числа \(t_i\) — время нанесения удара \(i\)-й торпедой и \(x_i\) — координату удара \(i\)-й торпедой. Все \(t_i\) и \(x_i\) должны быть целыми, \(0\le t_i\le 10^{18}\), \(-10^{18}\le x_i\le 10^{18}\). В один момент времени можно выпускать несколько торпед, в одну точку можно выпускать несколько торпед в разные моменты времени.
Решения, правильно работающие при \(N + M \leq 10\), \(0 \leq l_i \leq 100\), \(0 \leq r_i \leq 100\), будут оцениваться в 20 баллов.
Решения, правильно работающие при \(N + M \leq 1000\), будут оцениваться в 50 баллов.
В примере из условия два корабля движутся влево и один корабль движется вправо. Начальные координаты кораблей, двигающихся влево, равны \(l_1=10\) и \(l_2=30\), а начальная координата корабля, двигающегося вправо, равна \(r_1=20\). В момент времени \(t_1=5\) в одной точке \(x_1=25\) окажутся два корабля — двигающийся влево из точки \(20\) и двигающийся вправо из точки \(30\). Их можно подбить одной торпедой. Оставшийся корабль, двигающийся влево, можно подбить, например, в момент времени \(t_2=2\) в точке \(x_2=8\).
2 1 10 30 20
0 10 5 25