Background

Today I gave Atcoder ABC442. In problem E, I observed some analogy of setup of this problem with concepts of Linear Algebra.

Observations

1. Monsters are depicted as vectors in $$$\mathbb{R}^2$$$ From Linear Algebra perspective, every monster $$$i$$$ at coordinates $$$(X_i, Y_i)$$$ is a vector $$$\mathbf{v}_i = \begin{bmatrix} X_i \ Y_i \end{bmatrix}$$$ in the vector space $$$\mathbb{R}^2$$$.Takahashi stands at the origin (the zero vector $$$\mathbf{0}$$$). When he faces a monster, he is aligning his "sight vector" with the subspace spanned by that monster's vector.

2. Linearity and Collinearity (The "Same Direction" Check)The problem frequently asks if two monsters are in the "same direction." In Linear Algebra, two non-zero vectors $$$\mathbf{u}$$$ and $$$\mathbf{v}$$$ are collinear (linearly dependent) if one is a scalar multiple of the other:

\det(\mathbf{u}, \mathbf{v}) = x_u y_v — x_v y_u$$$$If $$$\det(\mathbf{u}, \mathbf{v}) = 0$, the vectors lie on the same line.To check if they are in the same direction (same ray from origin), we also need the dot product $$$\mathbf{u} \cdot \mathbf{v} = x_u x_v + y_u y_v$$$ to be positive.

1. Basis Transformation and Sorting (Ordering the Monsters)The core difficulty is sorting vectors clockwise or counter-clockwise. This is essentially ordering vectors by their angle in the polar coordinate system.While we typically use atan2, Linear Algebra offers a purely algebraic way to sort vectors using Basis Partitioning and Cross Products:Quadrant/Basis Partitioning:The space $$$\mathbb{R}^2$$$ is divided by the standard basis vectors $$$\mathbf{i} = (1,0)$$$ and $$$\mathbf{j} = (0,1)$$$.We can partition the plane into two half-planes (Upper and Lower) based on the sign of the y-component (and x-component if y is 0). This is a rough sort.Fine Sorting via Determinant:Within the same half-plane, we determine the relative order of any two vectors $$$\mathbf{u}$$$ and $$$\mathbf{v}$$$ using the determinant $$$\det(\mathbf{u}, \mathbf{v})$$$ (the "cross product").If $$$\det(\mathbf{u}, \mathbf{v}) \gt 0$$$, the linear transformation mapping $$$\mathbf{i}$$$ to $$$\mathbf{u}$$$ and $$$\mathbf{j}$$$ to $$$\mathbf{v}$$$ preserves orientation, meaning $$$\mathbf{v}$$$ is "counter-clockwise" from $$$\mathbf{u}$$$ (via the right-hand rule).This allows us to implement a comparator for sorting std::sort without ever calculating an actual angle or using pi, avoiding floating-point errors entirely.

2. Mathematical Optimization: Canonical FormsTo solve the "same direction" issue efficiently, we can normalize vectors to their Canonical Form.For any vector $$$\mathbf{v} = (x, y)$$$ with integer coordinates, we can map it to a unique representative $$$\mathbf{v}'$$$ for the ray it generates:$$\mathbf{v}' = \left( \frac{x}{\gcd(|x|, |y|)}, \frac{y}{\gcd(|x|, |y|)} \right)

   Unable to parse markup [type=CF_MATHJAX]

   \mathbb{Q}^2$ (rational coordinate space). This allows us to group monsters using a hash map or simple equality checks rather than geometric range checks.