C. Careful Maneuvering

有两个小型宇宙飞船，被两组敌方大型宇宙飞船包围。空间是一个二维平面，其中一组敌方飞船的位置满足：它们的 $y$-坐标均为整数，且 $x$-坐标为 $-100$；另一组敌方飞船的位置满足：它们的 $y$-坐标均为整数，且 $x$-坐标为 $100$。 两个组中的每一艘敌方飞船将同时向两艘小型飞船各发射一束激光（无限延伸的射线，触碰到任何飞船即摧毁之），所有激光同时发射。小型飞船能够避开所有激光，现在希望将它们定位在 $x = 0$ 上的某些位置（$y$-坐标不一定是整数），使得射向它们的激光能够摧毁尽可能多的敌方飞船。请找出在这种方式下能够摧毁的敌方飞船的最大数量，假设敌方飞船无法躲避激光。 第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 60$），分别表示 $x = -100$ 和 $x = 100$ 上的敌方飞船数量。 第二行包含 $n$ 个整数 $y_{1,1}, y_{1,2}, dots.h, y_{1,n}$（$| y_{1,i} | lt.eq 10\ 000$）——第一组飞船的 $y$-坐标。 第三行包含 $m$ 个整数 $y_{2,1}, y_{2,2}, dots.h, y_{2,m}$（$| y_{2,i} | lt.eq 10\ 000$）——第二组飞船的 $y$-坐标。 $y$ 坐标在组内也可能不唯一。 请输出一个整数——能够被摧毁的敌方飞船的最大数量。 在第一个例子中，第一艘小型飞船可定位在 $(0, 2)$，第二艘可定位在 $(0, 7)$。这样，第一组的所有敌方飞船和第二组中的 $6$ 艘飞船将被摧毁。 在第二个例子中，第一艘小型飞船可定位在 $(0, 3)$，第二艘可定位在任意位置，即可摧毁所有敌方飞船。 ## Input 第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 60$），分别表示 $x = -100$ 和 $x = 100$ 上的敌方飞船数量。第二行包含 $n$ 个整数 $y_{1,1}, y_{1,2}, dots.h, y_{1,n}$（$| y_{1,i} | lt.eq 10\ 000$）——第一组飞船的 $y$-坐标。第三行包含 $m$ 个整数 $y_{2,1}, y_{2,2}, dots.h, y_{2,m}$（$| y_{2,i} | lt.eq 10\ 000$）——第二组飞船的 $y$-坐标。$y$ 坐标在组内也可能不唯一。 ## Output 请输出一个整数——能够被摧毁的敌方飞船的最大数量。 [samples] ## Note 在第一个例子中，第一艘小型飞船可定位在 $(0, 2)$，第二艘可定位在 $(0, 7)$。这样，第一组的所有敌方飞船和第二组中的 $6$ 艘飞船将被摧毁。在第二个例子中，第一艘小型飞船可定位在 $(0, 3)$，第二艘可定位在任意位置，即可摧毁所有敌方飞船。

Let $ A = \{a_1, a_2, \dots, a_n\} $ be the set of $ y $-coordinates of enemy spaceships at $ x = -100 $, and $ B = \{b_1, b_2, \dots, b_m\} $ be the set of $ y $-coordinates of enemy spaceships at $ x = 100 $. Let $ p, q \in \mathbb{R} $ be the $ y $-coordinates of the two friendly small spaceships positioned on the line $ x = 0 $. Each enemy spaceship at $ (-100, a_i) $ is destroyed if the laser ray from $ (-100, a_i) $ to either $ (0, p) $ or $ (0, q) $ passes through it — which it always does by construction. However, **a single laser shot from an enemy spaceship destroys only one target** (one of the two small ships). But since **each enemy spaceship fires two lasers, one toward each small ship**, then **every enemy spaceship is destroyed if and only if at least one of the two laser rays it fires passes through the other enemy spaceship** (i.e., the ray from an enemy at $ (-100, a_i) $ to $ (0, p) $ may intersect another enemy at $ (100, b_j) $, and vice versa). Wait — clarification from problem: the small spaceships **avoid** all laser shots. So the lasers **do not hit the small ships**. But the lasers are infinite rays. The key is: **a laser shot fired from an enemy spaceship toward a small spaceship may intersect another enemy spaceship along its path**. If so, that **other** enemy spaceship is destroyed. So: each enemy spaceship fires two lasers: one toward each small ship. Each laser is a ray from the enemy’s position through the small ship’s position, extending infinitely beyond. If this ray passes through **any other enemy spaceship** (from either group), that enemy is destroyed. Therefore, an enemy at $ (-100, a_i) $ destroys: - All enemy spaceships lying on the ray from $ (-100, a_i) $ through $ (0, p) $ - All enemy spaceships lying on the ray from $ (-100, a_i) $ through $ (0, q) $ Similarly, an enemy at $ (100, b_j) $ destroys: - All enemy spaceships lying on the ray from $ (100, b_j) $ through $ (0, p) $ - All enemy spaceships lying on the ray from $ (100, b_j) $ through $ (0, q) $ Note: the ray from $ (-100, a_i) $ through $ (0, p) $ has slope $ \frac{p - a_i}{100} $, and continues to $ x = 100 $, where it has $ y = a_i + 2p - 2a_i = 2p - a_i $. So at $ x = 100 $, it intersects the line $ y = 2p - a_i $. Therefore, the ray from $ (-100, a_i) $ through $ (0, p) $ will hit enemy spaceship $ (100, b_j) $ if and only if: $$ b_j = 2p - a_i $$ Similarly, the ray from $ (100, b_j) $ through $ (0, p) $ will hit enemy spaceship $ (-100, a_i) $ if and only if: $$ a_i = 2p - b_j $$ Which is the same condition: $ a_i + b_j = 2p $ Similarly for $ q $: $ a_i + b_j = 2q $ Thus, **an enemy at $ (-100, a_i) $ and an enemy at $ (100, b_j) $ are mutually destroyed by each other’s laser if and only if $ a_i + b_j = 2p $ or $ a_i + b_j = 2q $**. But note: **each enemy spaceship fires two lasers**, one toward each small ship. So the enemy at $ (-100, a_i) $ fires a laser toward $ (0,p) $, which destroys **all** enemies on that ray — i.e., all $ (100, b_j) $ such that $ b_j = 2p - a_i $, and also all $ (-100, a_k) $ such that the ray from $ (-100, a_i) $ through $ (0,p) $ passes through $ (-100, a_k) $? But all enemies in group 1 are on the same vertical line $ x = -100 $, so the ray from $ (-100, a_i) $ through $ (0,p) $ goes diagonally and will not pass through any other point on $ x = -100 $, unless $ a_k = a_i $ — but even then, the ray starts at $ (-100, a_i) $, so unless another enemy is at the same point, it won't be hit. But the problem says: “the rays shot at them would destroy as many of the enemy spaceships as possible”, and “enemy spaceships can't avoid laser shots”. Crucially: **a laser shot fired from one enemy spaceship travels in a straight line toward a small ship, and continues infinitely. If it passes through any other enemy spaceship (from either group) along its path, that enemy is destroyed.** So: - A laser from $ (-100, a_i) $ toward $ (0, p) $ travels along the line from $ (-100, a_i) $ to $ (0, p) $, and beyond. It will intersect the line $ x = 100 $ at point $ (100, 2p - a_i) $. So it will destroy **all** enemy spaceships in group B at $ y = 2p - a_i $. - Does it destroy any other enemy in group A? The ray starts at $ (-100, a_i) $ and goes to $ (0,p) $. For another enemy at $ (-100, a_k) $, $ k \ne i $, to lie on this ray, the ray would have to pass through two points on the same vertical line — which is impossible unless $ a_k = a_i $, but even then, the ray starts at $ (-100, a_i) $, so if $ a_k = a_i $, then $ (-100, a_k) $ is the same point — so if multiple enemies are at the same coordinate, they are at the same location, and firing from one destroys the others at the same point? But the problem says “the enemy spaceships can't avoid laser shots”, and “destroy any spaceship it touches”. So if two enemies are at the same point $ (-100, a_i) $, and one fires a laser, does it destroy the other? The laser originates from that point — so if another enemy is at the exact same location, then yes, it is destroyed. But the problem says “the rays shot at them” — meaning the small ships — so the laser is aimed at the small ship, but starts at the enemy. So if multiple enemies are co-located, then a laser fired from one will destroy all others at the same point, because the ray starts there. But typically in such problems, we assume that if multiple entities are at the same point, then any laser passing through that point destroys all of them. So we can treat the set $ A $ and $ B $ as **multisets**. Therefore, the destruction mechanism is: - For a given position $ p $ of a small ship, the laser from enemy $ (-100, a_i) $ toward $ p $ destroys: - All enemies in group B at $ y = 2p - a_i $ - All enemies in group A at $ y = a_i $ (but only if they are at the same point — i.e., multiplicity) Wait — but the ray starts at $ (-100, a_i) $. So it destroys **all enemies lying on the ray**, including the one it started from? Probably not — the laser is shot *from* that enemy, so it doesn’t destroy itself. But it may destroy other enemies at the same location if they are present. Standard interpretation in such problems: a laser fired from a point destroys all other objects lying on the ray, **not** the origin. So: **a laser from $ (-100, a_i) $ toward $ (0,p) $ destroys all enemy spaceships (from either group) that lie on the ray segment starting at $ (-100, a_i) $ and extending through $ (0,p) $ and beyond, excluding the origin**. Therefore: - It can destroy enemies in group B: those at $ (100, b_j) $ such that $ b_j = 2p - a_i $ - It **cannot** destroy any other enemy in group A, because any other enemy in group A is at $ (-100, a_k) $, which is on the same vertical line. The ray from $ (-100, a_i) $ to $ (0,p) $ has direction vector $ (100, p - a_i) $, so it leaves the line $ x = -100 $ immediately. So no other point on $ x = -100 $ lies on the ray except the origin. Similarly, a laser from $ (100, b_j) $ toward $ (0,p) $ destroys only enemies in group A at $ a_i = 2p - b_j $, and no other enemy in group B. Therefore, the only possible mutual destructions are **between group A and group B**. Specifically: - A laser from $ (-100, a_i) $ to $ (0,p) $ destroys all $ (100, b_j) $ with $ b_j = 2p - a_i $ - A laser from $ (100, b_j) $ to $ (0,p) $ destroys all $ (-100, a_i) $ with $ a_i = 2p - b_j $ But note: if $ a_i + b_j = 2p $, then the laser from $ (-100, a_i) $ to $ (0,p) $ destroys $ (100, b_j) $, and the laser from $ (100, b_j) $ to $ (0,p) $ destroys $ (-100, a_i) $. So **both are destroyed**. But each enemy fires two lasers: one to each small ship. So for each enemy, it fires two rays. Each ray may destroy multiple enemies in the other group. The total number of destroyed enemy spaceships is the union of all enemies hit by any of the four rays (two from each small ship’s direction). Let $ p $ and $ q $ be the two small ship positions. Define: - $ D_p^A = \{ b \in B \mid \exists a \in A \text{ s.t. } a + b = 2p \} $ — enemies in B destroyed by lasers from A aimed at $ p $ - $ D_p^B = \{ a \in A \mid \exists b \in B \text{ s.t. } a + b = 2p \} $ — enemies in A destroyed by lasers from B aimed at $ p $ Similarly for $ q $. But note: a single laser from an enemy in A toward $ p $ destroys all enemies in B with $ b = 2p - a $. So if multiple $ a $'s map to the same $ b $, then that $ b $ is destroyed by multiple lasers, but it’s still destroyed once. So the set of destroyed enemies in B by lasers toward $ p $ is: $$ D_p^B = \{ b \in B \mid b = 2p - a \text{ for some } a \in A \} $$ Similarly, destroyed in A by lasers toward $ p $: $$ D_p^A = \{ a \in A \mid a = 2p - b \text{ for some } b \in B \} $$ But note: $ a = 2p - b \iff a + b = 2p $, same as above. So the set of destroyed enemies from group A due to lasers aimed at $ p $ is: $$ D_p^A = \{ a \in A \mid \exists b \in B \text{ such that } a + b = 2p \} $$ Similarly, destroyed from group B due to lasers aimed at $ p $: $$ D_p^B = \{ b \in B \mid \exists a \in A \text{ such that } a + b = 2p \} $$ Same for $ q $: $ D_q^A $, $ D_q^B $ Then total destroyed enemies = $ |D_p^A \cup D_q^A| + |D_p^B \cup D_q^B| $ We are to choose $ p, q \in \mathbb{R} $ to **maximize** this sum. Note: since $ p $ and $ q $ are real numbers, and $ A, B $ are finite sets of integers, the values $ 2p $ and $ 2q $ can be chosen to be any real numbers. But the condition $ a + b = 2p $ only holds for specific values of $ 2p $ — namely, the values $ a_i + b_j $ for some $ i,j $. Therefore, the only values of $ p $ that can destroy any enemy are those for which $ 2p \in S $, where $ S = \{ a_i + b_j \mid a_i \in A, b_j \in B \} $ Similarly for $ q $. So we can restrict $ 2p $ and $ 2q $ to be elements of $ S $, or possibly other values? But if $ 2p \notin S $, then $ D_p^A = \emptyset $ and $ D_p^B = \emptyset $, so it contributes nothing. So we can assume $ 2p, 2q \in S $. Thus, define $ T = \{ a_i + b_j \mid a_i \in A, b_j \in B \} $ We are to choose two values $ s_1, s_2 \in T \cup \{ \text{anything} \} $, but as above, only values in $ T $ matter. So choose $ s_1, s_2 \in T $, and define: - $ A_{s} = \{ a \in A \mid \exists b \in B \text{ s.t. } a + b = s \} $ - $ B_{s} = \{ b \in B \mid \exists a \in A \text{ s.t. } a + b = s \} $ Then for two chosen sums $ s_1, s_2 \in T $, total destroyed = $ |A_{s_1} \cup A_{s_2}| + |B_{s_1} \cup B_{s_2}| $ We want to maximize this over all $ s_1, s_2 \in T $ Note: $ s_1 $ and $ s_2 $ can be equal. This is now a finite problem: $ |T| \leq n \cdot m \leq 60 \cdot 60 = 3600 $, which is manageable. So algorithm: 1. Compute the set $ T = \{ a_i + b_j \mid a_i \in A, b_j \in B \} $ 2. For each $ s \in T $, precompute: - $ A_s = \{ a \in A \mid \exists b \in B \text{ s.t. } a + b = s \} $ - $ B_s = \{ b \in B \mid \exists a \in A \text{ s.t. } a + b = s \} $ 3. Iterate over all pairs $ (s_1, s_2) \in T \times T $ 4. Compute $ |A_{s_1} \cup A_{s_2}| + |B_{s_1} \cup B_{s_2}| $ 5. Take the maximum We can optimize by noting that $ A_s $ and $ B_s $ can be represented as sets, and we can use bit masks or simply iterate since $ n, m \leq 60 $, and $ |T| \leq 3600 $, so $ |T|^2 \leq 13 \text{ million} $, which is acceptable in C++/Python if optimized. But we can do better: since $ n, m \leq 60 $, we can precompute for each $ s \in T $ the sets $ A_s $ and $ B_s $ as bitsets or boolean arrays, and then use set union. Alternatively, since the sizes are small, we can just use Python sets. But the problem says: “Print a single integer” So final formal statement: Let $ A \subseteq \mathbb{Z} $, $ |A| = n $, $ B \subseteq \mathbb{Z} $, $ |B| = m $ Let $ T = \{ a + b \mid a \in A, b \in B \} $ For each $ s \in T $, define: - $ A_s = \{ a \in A \mid \exists b \in B \text{ s.t. } a + b = s \} $ - $ B_s = \{ b \in B \mid \exists a \in A \text{ s.t. } a + b = s \} $ Find: $$ \max_{s_1, s_2 \in T} \left( |A_{s_1} \cup A_{s_2}| + |B_{s_1} \cup B_{s_2}| \right) $$ This is the maximum number of enemy spaceships that can be destroyed.