Codeforces Round 488 by NEAR (Div. 1) |
---|
Закончено |
Два небольших космических корабля окружены двумя группами вражеских больших космических кораблей. Все происходит на плоскости, и одна группа вражеских кораблей расположена так, что все $$$y$$$-координаты их кораблей целочисленные, а $$$x$$$-координаты равны $$$-100$$$, в то время как у второй группы вражеских кораблей тоже $$$y$$$-координаты целочисленны, но их $$$x$$$-координаты равны $$$100$$$.
Каждый корабль в обеих группах одновременно сделает два выстрела из лазера (такой выстрел – это бесконечный луч, который уничтожает любой корабль на своем пути): по одному точно в направлении каждого маленького космического корабля. Все выстрелы будут сделаны одновременно. Маленькие космические корабли смогут легко увернуться от этих выстрелов, и сейчас хотят расположить себя в каких-то позициях с $$$x=0$$$ (и не обязательно целыми $$$y$$$), чтобы эти лучи уничтожили как можно больше вражеских кораблей. Найдите максимальное количество вражеских кораблей, которые можно так уничтожить, считая, что вражеские корабли не смогут увернуться.
В первой строке находятся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 60$$$) — количество вражеских кораблей группе с $$$x = -100$$$ и количество вражеских кораблей в группе c $$$x = 100$$$, соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$y_{1,1}, y_{1,2}, \ldots, y_{1,n}$$$ ($$$|y_{1,i}| \le 10\,000$$$) — $$$y$$$-координаты кораблей в первой группе.
Третья строка содержит $$$m$$$ целых чисел $$$y_{2,1}, y_{2,2}, \ldots, y_{2,m}$$$ ($$$|y_{2,i}| \le 10\,000$$$) — $$$y$$$-координаты кораблей во второй группе.
$$$y$$$-координаты не обязательно уникальны, даже в пределах одной группы.
Выведите одно число — максимальное количество вражеских кораблей, которое можно уничтожить.
3 9
1 2 3
1 2 3 7 8 9 11 12 13
9
5 5
1 2 3 4 5
1 2 3 4 5
10
В первом примере один корабль может расположиться в $$$(0, 2)$$$, а второй – в $$$(0, 7)$$$. Так все корабли в первой группе и $$$6$$$ из $$$9$$$ кораблей во второй группе будут уничтожены.
Во втором примере один корабль может расположиться в $$$(0, 3)$$$, а второй – в любом месте, этого будет достаточно, чтобы уничтожить все вражеские корабли.
Название |
---|