关于坐标系旋转的小trick

· · 算法·理论

这个 trick 算是比较经典的一种，而且属于基本上看到后就会记住，而且特征非常的明显。

简述

对于某一类特定的题目，会有多个点在特定的一类图上按照固定的方向做匀速运动的题目，我们可以通过以时间为横坐标，特定的内容（如深度，位置）为纵坐标来使用坐标轴进行刻画。此时我们可以发现直线都是形如 y=x 或者 y=-x 的样子。

据野史考究，这个小技巧最早出现 NOI2008 糖果雨，具体我也不清楚。

旋转变换坐标系

首先我们先来看进行旋转后的坐标变化：

对于原坐标为 (x,y) ,考虑逆时针旋转 \frac{\pi}{4} 的变化：

将\theta = 45^\circ代入通用公式：

\begin{cases} x' = x\cos(45^\circ) - y\sin(45^\circ) \\ y' = x\sin(45^\circ) + y\cos(45^\circ) \end{cases}

代入三角函数值化简：

\begin{cases} x' = x \cdot \frac{\sqrt{2}}{2} - y \cdot \frac{\sqrt{2}}{2} \\ y' = x \cdot \frac{\sqrt{2}}{2} + y \cdot \frac{\sqrt{2}}{2} \end{cases}

最终得到公式：

\begin{cases} x' = \dfrac{\sqrt{2}}{2}(x - y) \\[4pt] y' = \dfrac{\sqrt{2}}{2}(x + y) \end{cases}

我们考虑将坐标长度等比放大 \sqrt{2} 倍，此时就是整点了，我们可以求出点 (x,y) \to (x+y,x-y)。

题目一 树上行走

我们需要找到一个快速的方法来表示对于每个时刻每个人的位置，我们可以考虑在坐标轴上刻画这个操作。

我们以时间为横坐标，深度为纵坐标来建立坐标系，不难发现每次移动都是在坐标系上做斜率为 \pm 1。

我们对于斜线不是很好处理，于是考虑将斜线转化为直线，不难想到将坐标旋转 \frac{\pi}{4}。

此时我们可以将斜线转化为水平或者平行于坐标轴的直线，问题可以转化为：对每⼀条线段求出在线段上哪个点的相交次数最多？

于是可以顺利成章的对这个坐标轴两个方向分别做扫描线，于是题目就做完了。

题目二 保镖

本题也是一个卡时旋转坐标系的好题，感觉也是一个拼好题。

我们考虑类比上一题，以时间--位置为横纵坐标。此时不难发现每次移动都是在坐标系上做斜率为 \pm 1。

于是还是旋转坐标系，变成垂直或水平的直线，然后对坐标进行一次离散化。

由于我们线段的长度发生了变化，此时我们将 c_i 统一减去一半来抵消伸缩变换的影响。

然后我们只有 n^2 个节点了，我们考虑做 dp。

我们定义： f_{i,j} 表示从 (i,j) 开始走，可获得的最大价值。然后的转移，就是枚举下一个往上走还是右走，然后选择最大的进行保护。

剩下的就是另一个问题了，我们发现保镖不一定在格点上！

询问点之后的第一条横线和纵线。最优情况一定是从起点到这两条线上某个离散化点的收益加上该点的最大收益。

不难发现最大收益形如 f_{i,l}+c_{i,l}(l_i-l) ，我们可以对于两组情况分别处理，用李超线段树处理最值，然后每次暴力重构即可！

上一个题目是以时间--位置为横纵坐标，这不由得会联想到一个新题目：

题目三 P15246 [WC2026] 猫和老鼠

我们不难发现我们还可以延续上一个题的方法，于是可以把题目转化为：是否存在从左下走到右上，且穿越不超过 k 条线段的路径。

对于 w=0 的情况，我们使用线段树来优化 dp ,这部分大家去看题解吧。

我们可以刻画出上图的情况，我们可以考虑对这些图定向，也就是说，需要找出一条如下路径：从左上边界出发，可以任意向左或向上，或根据机械猫形成的线段向右或向下，直到抵达右下边界。

对于第二类很明显，对于第一类我们可以看直线 s，会发现如果有一个端点在左上方的点一定不会更劣！

于是我们可以考虑建图，对于 N 较小时候我们可以直接暴力和左上的点连线，以及和相交的直线进行连线，对于两个边界，我们可以建立源点与汇点连距离为 0 的点来做最短路和网络流。

对于 N 比较大的情况，我们会很自然的考虑优化建图，发现每次都会和左面一个区间的点进行连线，我们于是可以艰难的过这个题目了。

具体内容可以移步该题目题解 耗子与猫题解

总结

这个小技巧个人感觉没必要练习太多的题目，且样貌明显。一般都会衔接如扫描线，dp，最短路，网络流等算法综合考察。