E. The Supersonic Rocket

[{"iden":"statement","content":"战争结束后，超音速火箭成为最常见的公共交通工具。\n\n每艘超音速火箭由*两个*“_引擎_”组成。每个引擎是一组“_动力源_”。第一个引擎有 $n$ 个动力源，第二个引擎有 $m$ 个动力源。一个动力源可以描述为二维平面上的一个点 $(x_i, y_i)$。每个引擎中的所有点均不相同。\n\n你可以分别操纵每个引擎。你对每个引擎可以执行两种操作，每种操作可以执行任意多次。\n\n引擎的工作方式如下：当两个引擎启动后，它们的动力源将被合并（此处不同引擎的动力源可能重合）。如果存在两个动力源 $A (x_a, y_a)$ 和 $B (x_b, y_b)$，那么对于所有满足 $0 lt k lt 1$ 的实数 $k$，都会生成一个新的动力源 $C_k (k x_a + (1 -k) x_b, k y_a + (1 -k) y_b)$。*然后，此过程会再次对所有新生成和原有的动力源重复进行*。之后，将从所有动力源生成“_动力场_”（可视为所有出现的动力源构成的无限集合）。\n\n一艘超音速火箭是“_安全的_”，当且仅当在你操纵引擎后，移除任意一个动力源再启动引擎，生成的动力场不会改变（与没有任何动力源被删除的情况相比）。两个动力场被视为相同，当且仅当其中一个场中的任意动力源也属于另一个场。\n\n给定一艘超音速火箭，判断它是否安全。\n\n第一行包含两个整数 $n$, $m$ ($3 lt.eq n, m lt.eq 10^5$) —— 每个引擎的动力源数量。\n\n接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 lt.eq x_i, y_i lt.eq 10^8$) —— 第一个引擎中第 $i$ 个动力源的坐标。\n\n接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 lt.eq x_i, y_i lt.eq 10^8$) —— 第二个引擎中第 $i$ 个动力源的坐标。\n\n保证每个引擎中不存在两个或更多位于同一点的动力源。\n\n如果超音速火箭是安全的，请输出“_YES_”，否则输出“_NO_”。\n\n你可以以任意大小写形式输出每个字母。\n\n第一个样例：\n\n首先，操纵第一个引擎：使用第二个操作，令 $theta = pi$（将所有动力源旋转 $180$ 度）。\n\n第一个引擎中的动力源变为 $(0, 0)$、$(0, -2)$ 和 $(-2, 0)$。\n\n其次，操纵第二个引擎：使用第一个操作，令 $a = b = -2$。\n\n第二个引擎中的动力源变为 $(-2, 0)$、$(0, 0)$、$(0, -2)$ 和 $(-1, -1)$。\n\n你可以验证，无论移除哪一个点，两个引擎形成的动力场始终是实心三角形 $(0, 0)$、$(-2, 0)$、$(0, -2)$。\n\n在第二个样例中，无论你如何操纵引擎，第二个引擎中总存在一个动力源，若将其删除，动力场将缩小。 \n\n"},{"iden":"input","content":"第一行包含两个整数 $n$, $m$ ($3 lt.eq n, m lt.eq 10^5$) —— 每个引擎的动力源数量。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 lt.eq x_i, y_i lt.eq 10^8$) —— 第一个引擎中第 $i$ 个动力源的坐标。接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 lt.eq x_i, y_i lt.eq 10^8$) —— 第二个引擎中第 $i$ 个动力源的坐标。保证每个引擎中不存在两个或更多位于同一点的动力源。"},{"iden":"output","content":"如果超音速火箭是安全的，请输出“_YES_”，否则输出“_NO_”。你可以以任意大小写形式输出每个字母。"},{"iden":"examples","content":"输入\n3 4\n0 0\n0 2\n2 0\n0 2\n2 2\n2 0\n1 1\n输出\nYES\n\n输入\n3 4\n0 0\n0 2\n2 0\n0 2\n2 2\n2 0\n0 0\n输出\nNO"},{"iden":"note","content":"第一个样例： #cf_span(class=[tex-font-size-small], body=[那些靠近的蓝色和橙色点实际上重合。]) 首先，操纵第一个引擎：使用第二个操作，令 $theta = pi$（将所有动力源旋转 $180$ 度）。第一个引擎中的动力源变为 $(0, 0)$、$(0, -2)$ 和 $(-2, 0)$。其次，操纵第二个引擎：使用第一个操作，令 $a = b = -2$。第二个引擎中的动力源变为 $(-2, 0)$、$(0, 0)$、$(0, -2)$ 和 $(-1, -1)$。你可以验证，无论移除哪一个点，两个引擎形成的动力场始终是实心三角形 $(0, 0)$、$(-2, 0)$、$(0, -2)$。在第二个样例中，无论你如何操纵引擎，第二个引擎中总存在一个动力源，若将其删除，动力场将缩小。 "}]}

**Definitions** Let $ A = \{a_1, a_2, \dots, a_n\} \subset \mathbb{R}^2 $ be the set of power sources of the first engine. Let $ B = \{b_1, b_2, \dots, b_m\} \subset \mathbb{R}^2 $ be the set of power sources of the second engine. Let $ \text{conv}(S) $ denote the convex hull of a set $ S \subset \mathbb{R}^2 $. Let $ \text{aff}(S) $ denote the affine hull of $ S $. Let $ \text{span}(S) $ denote the linear span of $ S - s_0 $ for some $ s_0 \in S $ (i.e., the vector space generated by differences of points in $ S $). Define the **closure under affine combinations** of a set $ S \subset \mathbb{R}^2 $ as: $$ \overline{S} = \left\{ \sum_{i=1}^k \lambda_i s_i \,\middle|\, k \in \mathbb{N},\, s_i \in S,\, \lambda_i \in \mathbb{R},\, \sum_{i=1}^k \lambda_i = 1 \right\} $$ This is the affine hull of $ S $, i.e., $ \overline{S} = \text{aff}(S) $. The **power field** generated by engine sets $ A $ and $ B $ is: $$ \mathcal{P} = \overline{A \cup B} $$ **Operations allowed on each engine (independently):** 1. **Translation**: Add a fixed vector $ v \in \mathbb{R}^2 $ to all points in the engine. 2. **Linear transformation**: Apply an invertible linear transformation $ T \in \text{GL}(2,\mathbb{R}) $ to all points in the engine. *(Note: The problem allows arbitrary affine transformations preserving affine structure — translation and linear maps generate the full affine group.)* Thus, each engine’s set can be transformed to any **affinely equivalent** set: - $ A \mapsto T(A) + v $, for any $ T \in \text{GL}(2,\mathbb{R}) $, $ v \in \mathbb{R}^2 $. - Same for $ B $. **Constraints** 1. $ 3 \leq n, m \leq 10^5 $ 2. All points in $ A $ are distinct. 3. All points in $ B $ are distinct. 4. Coordinates are integers in $ [0, 10^8] $. **Objective** Determine whether there exist affine transformations $ f, g : \mathbb{R}^2 \to \mathbb{R}^2 $ such that the resulting power field $ \mathcal{P}' = \overline{f(A) \cup g(B)} $ satisfies: > For every point $ p \in f(A) \cup g(B) $, removing $ p $ does **not** change the affine hull: $$ \overline{f(A) \cup g(B)} = \overline{(f(A) \cup g(B)) \setminus \{p\}} $$ That is, **every point in the union is affine-dependent** on the others. This condition holds **if and only if** the entire set $ f(A) \cup g(B) $ is contained in an **affine subspace of dimension ≤ 1**, and **no point is isolated** — meaning the entire set lies on a single line, and has at least three points (so removing any one still leaves the affine hull unchanged). But since both $ A $ and $ B $ have at least 3 points, and we can apply arbitrary affine transformations to each, the key is: > The rocket is **safe** if and only if **both** $ A $ and $ B $ are **collinear** (i.e., all points lie on a straight line), and **after transformation**, their union lies on the same line. But note: we can independently transform each engine. So: - We can transform $ A $ to lie on any line $ \ell_1 $, - We can transform $ B $ to lie on any line $ \ell_2 $, - We want $ \overline{f(A) \cup g(B)} = \overline{f(A)} = \overline{g(B)} $, and **every point is redundant**. The only way **removing any point leaves the affine hull unchanged** is if the entire set lies in an affine space of dimension **at most 1**, and has **at least 3 points** (which it does). Moreover, since we can independently apply affine transformations to $ A $ and $ B $, we can make them lie on **any** two lines. To have their union lie on a single line, we must be able to map **both** $ A $ and $ B $ to subsets of the **same** line. But any finite set of at least 3 non-collinear points **cannot** be mapped by an affine transformation to a collinear set — because affine transformations preserve collinearity. Therefore: - $ f(A) $ is collinear **iff** $ A $ is collinear. - $ g(B) $ is collinear **iff** $ B $ is collinear. - $ f(A) \cup g(B) $ lies on a single line **iff** both $ A $ and $ B $ are collinear, and we can align their lines via translation/rotation — which we can, since we can rotate and translate each independently to lie on, say, the x-axis. So the **necessary and sufficient condition** is: > Both $ A $ and $ B $ are collinear sets. Then, after transforming both to lie on the same line, the union is a finite set of points on a line with at least 3 points (since $ n, m \geq 3 $), and thus every point is affine-dependent on the others → removing any point leaves the affine hull unchanged. If either $ A $ or $ B $ is **not** collinear, then $ \overline{A} $ or $ \overline{B} $ is 2-dimensional. After any affine transformation, $ f(A) $ or $ g(B) $ will still span a 2D affine space. Then $ \overline{f(A) \cup g(B)} $ is 2D. In a 2D affine set with at least 3 non-collinear points, **there exist extreme points** (e.g., vertices of convex hull) whose removal reduces the convex hull (and thus the affine hull). So the condition fails. Thus: **Objective (Formal)** The supersonic rocket is safe **if and only if** both $ A $ and $ B $ are collinear. That is: - The points of $ A $ lie on a single straight line. - The points of $ B $ lie on a single straight line. **Output** "YES" if both $ A $ and $ B $ are collinear; otherwise "NO". --- **Final Formal Statement** **Definitions** Let $ A = \{a_1, \dots, a_n\} \subset \mathbb{R}^2 $, $ B = \{b_1, \dots, b_m\} \subset \mathbb{R}^2 $, with $ n, m \geq 3 $, all points distinct. **Constraints** As given. **Objective** The rocket is safe **iff** $$ \dim(\text{aff}(A)) \leq 1 \quad \text{and} \quad \dim(\text{aff}(B)) \leq 1 $$ Output "YES" if both conditions hold; otherwise "NO".