Background
Today I gave Atcoder ABC442. In problem E, I observed some analogy of setup of this problem with concepts of Linear Algebra.
Observations
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.
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:$$\mathbf{v} = c \cdot \mathbf{u}
Unable to parse markup [type=CF_MATHJAX]
must be positive ($$$c \gt 0$$$).Instead of calculating slopes ($$$Y/X$$$) which risks division by zero, Linear Algebra uses the determinant (or 2D cross product) to check linear dependence.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.
Linear Algebra doesn't naturally have a "start" and "end" for angles like $$$0^\circ$$$ to $$$360^\circ$$$. Instead, we partition $$$\mathbb{R}^2$$$ into two half-planes (Upper and Lower) to create a strict linear order.Upper Half-Plane $$$H^+$$$: Vectors where $$$y \gt 0$$$ or ($$$y=0$$$ and $$$x \gt 0$$$).Lower Half-Plane $$$H^-$$$: Vectors where $$$y \lt 0$$$ or ($$$y=0$$$ and $$$x \lt 0$$$).Within each half-plane, the determinant uniquely determines the order.
