E. 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$ 艘（共 $9$ 艘）将被摧毁。 在第二个例子中，第一个小型飞船可置于 $(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$ 艘（共 $9$ 艘）将被摧毁。在第二个例子中，第一个小型飞船可置于 $(0, 3)$，第二个可置于任意位置，即可摧毁所有敌方飞船。

Let $ A = \{a_1, a_2, \dots, a_n\} $ be the set of $ y $-coordinates of enemy spaceships at $ x = -100 $. Let $ 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 small spaceships positioned on the line $ x = 0 $. Each enemy spaceship at $ (-100, a_i) $ fires two laser rays: one toward $ (0, p) $ and one toward $ (0, q) $. Similarly, each enemy spaceship at $ (100, b_j) $ fires two laser rays: one toward $ (0, p) $ and one toward $ (0, q) $. A laser ray from $ (-100, a_i) $ to $ (0, p) $ is the line segment (or ray) connecting these two points. This ray will destroy **all** enemy spaceships lying on the same line. Similarly for rays from $ (100, b_j) $ to $ (0, p) $ or $ (0, q) $. **Key Insight**: A laser shot from $ (-100, a_i) $ to $ (0, p) $ passes through a point $ (100, b_j) $ **if and only if** the three points are colinear. The slope from $ (-100, a_i) $ to $ (0, p) $ is $ \frac{p - a_i}{100} $. The slope from $ (-100, a_i) $ to $ (100, b_j) $ is $ \frac{b_j - a_i}{200} $. For colinearity with $ (0, p) $, we require: $$ \frac{p - a_i}{100} = \frac{b_j - a_i}{200} \quad \Rightarrow \quad 2(p - a_i) = b_j - a_i \quad \Rightarrow \quad b_j = 2p - a_i $$ Similarly, a ray from $ (100, b_j) $ to $ (0, p) $ passes through $ (-100, a_i) $ iff $ a_i = 2p - b_j $. Thus, **for a fixed $ p $, the set of enemy ships destroyed by the ray from $ (0,p) $** is: - All $ a_i \in A $ such that $ 2p - a_i \in B $, **and** - All $ b_j \in B $ such that $ 2p - b_j \in A $ In other words, the ray from $ (0, p) $ destroys all enemy ships $ a_i \in A $ and $ b_j \in B $ such that $ a_i + b_j = 2p $. Similarly, the ray from $ (0, q) $ destroys all $ a_i, b_j $ such that $ a_i + b_j = 2q $. Each enemy spaceship can be destroyed by **at most one** laser shot (since each fires two rays, but only one of them might hit another enemy, and we count destruction of enemies, not shots). But note: each enemy spaceship is hit if **any** of the four laser rays (two from each small ship) passes through it. So: An enemy at $ (-100, a_i) $ is destroyed if either: - $ a_i + b_j = 2p $ for some $ b_j \in B $, or - $ a_i + b_j = 2q $ for some $ b_j \in B $ Similarly, an enemy at $ (100, b_j) $ is destroyed if: - $ a_i + b_j = 2p $ for some $ a_i \in A $, or - $ a_i + b_j = 2q $ for some $ a_i \in A $ Therefore, the total number of destroyed enemy ships is the number of distinct values in $ A \cup B $ that appear in the set $ S = \{ a_i + b_j \mid a_i \in A, b_j \in B \} $, **and** such that their sum equals $ 2p $ or $ 2q $. Let $ T = \{ a_i + b_j \mid a_i \in A, b_j \in B \} $. Each value $ s \in T $ corresponds to a line (through $ (0, s/2) $) that destroys all enemy ships lying on that line: specifically, all $ a_i \in A $ and $ b_j \in B $ such that $ a_i + b_j = s $. But note: for a fixed $ s $, the number of **enemy ships destroyed** by the line $ x=0, y = s/2 $ is: - The number of $ a_i \in A $ such that $ \exists b_j \in B $ with $ a_i + b_j = s $, **plus** - The number of $ b_j \in B $ such that $ \exists a_i \in A $ with $ a_i + b_j = s $ But since $ s = a_i + b_j $, for each pair $ (a_i, b_j) $ with sum $ s $, **both** $ a_i $ and $ b_j $ are destroyed. However, if multiple pairs yield the same $ s $, we must count **distinct** enemy ships, not pairs. So for a fixed $ s \in T $, define: - $ A_s = \{ a_i \in A \mid \exists b_j \in B \text{ s.t. } a_i + b_j = s \} $ - $ B_s = \{ b_j \in B \mid \exists a_i \in A \text{ s.t. } a_i + b_j = s \} $ Then the number of enemy ships destroyed by choosing $ p = s/2 $ is $ |A_s \cup B_s| $? Wait — no: $ A_s \subseteq A $, $ B_s \subseteq B $, and $ A $ and $ B $ are disjoint sets (different x-coordinates), so $ A_s \cap B_s = \emptyset $. Thus, destroyed = $ |A_s| + |B_s| $. But note: $ A_s $ is the set of $ a_i \in A $ that participate in **at least one** pair summing to $ s $. Similarly for $ B_s $. So for each $ s \in T $, define: $$ d(s) = |\{ a_i \in A : \exists b_j \in B, a_i + b_j = s \}| + |\{ b_j \in B : \exists a_i \in A, a_i + b_j = s \}| $$ Then, if we choose two values $ s_1 = 2p $, $ s_2 = 2q $, the total number of destroyed enemy ships is: $$ d(s_1) + d(s_2) - | \text{enemy ships destroyed by both lines} | $$ An enemy ship might be destroyed by both lines if it lies on both lines — i.e., if $ a_i \in A_{s_1} \cap A_{s_2} $, or $ b_j \in B_{s_1} \cap B_{s_2} $. So we must subtract the overlap. Let $ D = \{ s \in T \} $, the set of all possible sums. We want to choose two values $ s_1, s_2 \in D $ (possibly $ s_1 = s_2 $) to maximize: $$ d(s_1) + d(s_2) - \left( |A_{s_1} \cap A_{s_2}| + |B_{s_1} \cap B_{s_2}| \right) $$ But note: if $ s_1 = s_2 $, then we are choosing the same point, so the two small spaceships are at the same location — which is allowed? The problem says "position themselves at some locations" — plural, but doesn't forbid same location. But if they are at the same location, then both shoot the same two rays? Actually, each small spaceship shoots two rays — one to each small spaceship. So if both small spaceships are at the same point $ (0,p) $, then each shoots one ray to the other — but that's the same ray. And each also shoots a ray to the other small spaceship — again, same ray. So effectively, only two rays are fired: both from each small ship to the common point. So we only get one line, not two. Wait — re-read: "Each spaceship in both groups will simultaneously shoot two laser shots (infinite ray that destroys any spaceship it touches), one towards each of the small spaceships" So each enemy ship shoots **two** rays: one to each small spaceship. So if the two small spaceships are at the same point $ (0,p) $, then each enemy ship shoots **two rays**, but **both rays are identical** — same direction. So the total set of rays is still just the set of rays from each enemy ship to $ (0,p) $ — so we get only one set of lines, not two. Thus, if $ p = q $, then we only get one line, and the total destroyed is $ d(s) $ for $ s = 2p $. If $ p \ne q $, then we get two distinct lines, and we destroy the union of the ships on both lines. So the problem reduces to: > Given sets $ A \subseteq \mathbb{Z} $, $ B \subseteq \mathbb{Z} $, and define for each $ s \in \mathbb{R} $: > $ d(s) = |\{ a \in A : \exists b \in B, a + b = s \}| + |\{ b \in B : \exists a \in A, a + b = s \}| $ > Let $ T = \{ a + b : a \in A, b \in B \} $ > Find $ \max_{s_1, s_2 \in T} \left[ d(s_1) + d(s_2) - |A_{s_1} \cap A_{s_2}| - |B_{s_1} \cap B_{s_2}| \right] $ But note: since $ A $ and $ B $ are finite (size ≤ 60), and $ |T| \leq 3600 $, we can iterate over all pairs $ (s_1, s_2) \in T \times T $. We can precompute: - For each $ s \in T $, compute: - $ A_s = \{ a \in A : \exists b \in B, a + b = s \} $ - $ B_s = \{ b \in B : \exists a \in A, a + b = s \} $ - $ d(s) = |A_s| + |B_s| $ Then for each pair $ (s_1, s_2) $, compute: $$ \text{total} = d(s_1) + d(s_2) - |A_{s_1} \cap A_{s_2}| - |B_{s_1} \cap B_{s_2}| $$ And take the maximum. Note: $ A_{s_1} \cap A_{s_2} $ is the set of $ a \in A $ such that $ a + b_1 = s_1 $ and $ a + b_2 = s_2 $ for some $ b_1, b_2 \in B $. But since $ s_1 \ne s_2 $, for a fixed $ a $, $ a + b = s_1 $ and $ a + b = s_2 $ can't both hold unless $ s_1 = s_2 $. So $ A_{s_1} \cap A_{s_2} $ is the set of $ a \in A $ such that there exist $ b_1, b_2 \in B $ with $ a + b_1 = s_1 $ and $ a + b_2 = s_2 $. That is, $ a $ appears in both $ A_{s_1} $ and $ A_{s_2} $, meaning $ a $ can form a sum $ s_1 $ with some $ b $, and $ s_2 $ with some (possibly different) $ b $. Same for $ B $. So the overlap is just the number of $ a \in A $ that are in both $ A_{s_1} $ and $ A_{s_2} $, and similarly for $ b \in B $. We can precompute for each $ a \in A $, the set of $ s \in T $ such that $ a + b = s $ for some $ b \in B $. Similarly for each $ b \in B $. Then for each pair $ (s_1, s_2) $, we can compute the intersection sizes by set operations. Since $ |T| \leq 3600 $, and $ |A|, |B| \leq 60 $, we can do $ O(|T|^2 \cdot |A|) $, which is about $ 3600^2 \cdot 60 \approx 777.6 \times 10^6 $ — borderline in C++ but in Python might be slow. But note: $ |T| \leq n \cdot m \leq 3600 $, but many sums may be repeated. Actually, the number of **distinct** sums is at most $ n \cdot m = 3600 $, but we can reduce by using a set. But 3600^2 = ~13 million pairs — which is acceptable in C++ or PyPy, and in Python if optimized. But we can optimize: instead of iterating over all pairs of sums, we can iterate over all possible pairs of enemy ship positions? No, better to stick with sum values. Alternatively, we can note that the optimal solution will choose $ s_1, s_2 $ from the set of distinct sums that actually occur. Let $ S = \text{set of distinct sums } a + b $ for $ a \in A, b \in B $. Let $ |S| \leq 3600 $. We can precompute: - For each $ s \in S $: $ A_s, B_s, d(s) $ - For each $ a \in A $, store $ \text{sums}_A[a] = \{ s \in S : a + b = s \text{ for some } b \in B \} $ - For each $ b \in B $, store $ \text{sums}_B[b] = \{ s \in S : a + b = s \text{ for some } a \in A \} $ Then for each pair $ (s_1, s_2) \in S \times S $: - $ \text{overlap}_A = \sum_{a \in A} \mathbf{1}_{s_1 \in \text{sums}_A[a] \text{ and } s_2 \in \text{sums}_A[a]} $ - Similarly for $ \text{overlap}_B $ But we can precompute for each $ a \in A $, the set of sums it belongs to, then for each pair $ (s_1, s_2) $, we can compute: - $ \text{overlap}_A = \sum_{a \in A} [s_1 \in \text{sums}_A[a] \text{ and } s_2 \in \text{sums}_A[a]] $ But that’s $ O(|A| \cdot |S|^2) \approx 60 \cdot 3600^2 \approx 777.6 \times 10^6 $, which is too slow in Python. Better: precompute a matrix $ M_A[s_1][s_2] = $ number of $ a \in A $ such that $ a \in A_{s_1} \cap A_{s_2} $ We can do: For each $ a \in A $, let $ \text{sums}_A[a] $ be the set of sums involving $ a $. Then for each pair $ (s_1, s_2) $, if $ s_1 \in \text{sums}_A[a] $ and $ s_2 \in \text{sums}_A[a] $, then increment $ M_A[s_1][s_2] $. We can iterate over all $ a \in A $, and for each $ a $, iterate over all pairs $ (s_1, s_2) $ in $ \text{sums}_A[a] \times \text{sums}_A[a] $. The number of sums per $ a $ is at most $ m \leq 60 $, so per $ a $, we do $ 60^2 = 3600 $ operations. Total for all $ a $: $ n \cdot 3600 \leq 60 \cdot 3600 = 216000 $ Same for $ B $: $ m \cdot 3600 \leq 216000 $ So total precomputation: ~432000 operations — very feasible. Then for each pair $ (s_1, s_2) \in S \times S $, we have: $$ \text{total}(s_1, s_2) = d(s_1) + d(s_2) - M_A[s_1][s_2] - M_B[s_1][s_2] $$ And we take the maximum over all $ s_1, s_2 \in S $. Note: $ s_1 $ and $ s_2 $ can be equal — then $ M_A[s_1][s_1] = |A_{s_1}| $, so: $$ \text{total}(s,s) = d(s) + d(s) - |A_s| - |B_s| = (|A_s| + |B_s|) + (|A_s| + |B_s|) - |A_s| - |B_s| = |A_s| + |B_s| = d(s) $$ Which is correct: if both small ships are at same point, we only get one line, destroying $ d(s) $ ships. So this formula works for $ s_1 = s_2 $. Thus, the algorithm: 1. Read $ n, m $, arrays $ A $, $ B $ 2. Compute $ T = \{ a + b \mid a \in A, b \in B \} $ → get set $ S $ of distinct sums 3. For each $ s \in S $: - $ A_s = \{ a \in A : \exists b \in B, a + b = s \} $ - $ B_s = \{ b \in B : \exists a \in A, a + b = s \} $ - $ d(s) = |A_s| + |B_s| $ 4. For each $ a \in A $, compute $ \text{sums}_A[a] = \{ s \in S : \exists b \in B, a + b = s \} $ 5. For each $ b \in B $, compute $ \text{sums}_B[b] = \{ s \in S : \exists a \in A, a + b = s \} $ 6. Initialize 2D arrays $ M_A, M_B $ of size $ |S| \times |S| $, indexed by sum values (use dict or map from sum to index) 7. For each $ a \in A $: - Let $ L_a = \text{sums}_A[a] $ - For each $ s_1 \in L_a $, for each $ s_2 \in L_a $: increment $ M_A[s_1][s_2] $ 8. Similarly for $ B $: for each $ b \in B $, for each $ s_1, s_2 \in \text{sums}_B[b] $: increment $ M_B[s_1][s_2] $ 9. Initialize $ \text{best} = 0 $ 10. For each $ s_1 \in S $, for each $ s_2 \in S $: - $ \text{score} = d(s_1) + d(s_2) - M_A[s_1][s_2] - M_B[s_1][s_2] $ - $ \text{best} = \max(\text{best}, \text{score}) $ 11. Print best Note: $ M_A[s_1][s_2] $ counts the number of $ a \in A $ that are in both $ A_{s_1} $ and $ A_{s_2} $ — which is exactly $ |A_{s_1} \cap A_{s_2}| $, same for $ B $. This is correct. We can use a dictionary mapping sum → index, or just use the sum value as key in a 2D dictionary. In Python, we can use `defaultdict(int)` for `M_A` and `M_B`. Let’s code accordingly. But note: the problem says "Print a single integer – the largest number of enemy spaceships that can be destroyed." We are done. **Final Formal Statement**: Given finite sets $ A, B \subseteq \mathbb{Z} $, define: - $ 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, a + b = s \} $ - $ B_s = \{ b \in B \mid \exists a \in A, a + b = s \} $ - $ d(s) = |A_s| + |B_s| $ - Define $ M_A(s_1, s_2) = |\{ a \in A \mid a \in A_{s_1} \cap A_{s_2} \}| $ - Define $ M_B(s_1, s_2) = |\{ b \in B \mid b \in B_{s_1} \cap B_{s_2} \}| $ Find: $$ \max_{s_1, s_2 \in T} \left( d(s_1) + d(s_2) - M_A(s_1, s_2) - M_B(s_1, s_2) \right) $$