企业官网建设流程全解析

我在AtCoder上第一次见到E - Laser Takahashi这道题时，第一反应是又要上什么旋转扫描、线段树、李超树之类的高级玩法。结果读完题面差点笑出声：题面绕来绕去，核心就一件事——把二维平面上一堆点，以某个中心点做顺时针极角排序。排序本身不难，难的是用叉乘去写这个sort比较器，一不留神就是WA、RE二选一。

这篇题解会把题目的推导、叉乘判断方向的原理、比较器每一行代码的用途，以及我实际踩过的坑完整过一遍。适合正在刷AtCoder ABC/ARC/AGC、准备区域赛的选手；如果你已经会用atan2排序但不知道为什么它在比赛里容易翻车，重点看第二节和第四节。如果你想知道怎么写一个不会被sort报错、纯整数运算的比较器，第三节的代码可以直接抄走。

1. 先弄明白题目到底在问什么

1.1 题面的大致意思

我按自己打比赛时常见的版本复述一下题面：原点处有一台激光装置，初始指向x轴正方向，开始后沿着顺时针方向匀速转动。平面上有N个敌人，每个敌人占据一个点。激光碰到第一个敌人就会停下，消灭它之后继续转动。要求输出这N个敌人被消灭的顺序，或者根据这个顺序求某个答案。

不同OJ的措辞可能会有小差别，比如激光会不会被同一射线上靠前的敌人挡住、激光是瞬时扫射还是匀速转动，但主干永远都是同一件事：把所有点按相对于原点的顺时针方向排好序。理解了这一点，题目后面的所有障碍就都集中到“怎么把一个比较器写对”上了。

1.2 为什么排序就是正解

最朴素的模拟做法是：记录当前激光方向，每次在所有还没被消灭的点里找一个角度最小（相对于当前方向）的点，消灭它，然后把方向更新到那个点。这个做法的时间复杂度是O(N^2)，N到2e5直接超时。

但仔细想一下：激光的转动顺序是固定的，不依赖前面消灭了谁。每个点到原点的方向向量，最终在极坐标系里都有一个确定的角度，让它们按角度从小到大（在这道题里是从x轴正方向开始顺时针一圈）排好，答案就已经出来了。整个问题退化成一个排序问题，复杂度O(N log N)，N开到2e5也完全能跑。

这里还藏着一个容易被忽略的细节：如果有两个敌人和原点在同一条射线上，激光扫过去会先碰到离原点更近的那个。所以排序的关键字不只是角度，而是“角度为主，距离为次”，距离近的排在前面。这个规则到写比较器时会直接影响代码。

2. 叉乘：判断两个向量相对方向的核心工具

2.1 二维叉乘到底在说什么

二维平面上的叉乘，虽然名字里带个“叉”，但结果是一个标量而不是向量。对两个从原点出发的向量a = (ax, ay)和b = (bx, by)，定义：

cross(a, b) = ax * by - ay * bx

这个值的正负含义非常重要：

• cross(a, b) > 0：b在a的逆时针方向；
• cross(a, b) < 0：b在a的顺时针方向；
• cross(a, b) = 0：a和b方向相同或者方向相反。

你可以把它想象成站在原点握着方向盘：如果现在车头朝a方向，你发现b在车头的左边，那cross就是正的；如果b在右边，cross就是负的。这个直观判断在写排序比较器的时候非常有用，因为sort最终要把“谁在谁前面”变成一个可比较的布尔值，而叉乘恰好给了我们这个布尔值。

注意坐标系必须是数学里默认的“x向右、y向上”的右手坐标系。如果题目用的是屏幕坐标系（y向下），叉乘的正负会反过来。AtCoder一般不会这么干，但遇到某些本地评测环境时值得多看一眼。

2.2 怎么构造一个正确的顺时针比较器

先给结论。C++的sort比较器返回true时，表示第一个参数a应该排在第二个参数b前面。为了让所有点从x轴正方向开始顺时针排列，比较器应该这样设计：

1. 先判断点落在哪个“半平面”；
2. 同一个半平面内用叉乘判断方向；
3. 叉乘为0时用距离判断谁先谁后。

这里的“半平面”不是数学书上那种y大于0的上下半平面，而是按从x轴正方向顺时针转180度的范围来切割。具体来说：

• 前半圈：y < 0，以及y = 0且x >= 0（包含x正半轴）；
• 后半圈：y > 0，以及y = 0且x < 0（包含x负半轴）。

这样划分的原因也很直接：我们要让排序从x轴正方向开始往下走，第一步自然进入第四象限，然后是y负半轴、第三象限，最后经过x负半轴进入第二象限和第一象限。如果把x正半轴分错到后半个半圈，排序出来的起点就不是题目要求的x轴正方向了。

同半平面内部，a应该在b前面的条件是：

cross(a, b) < 0

因为叉乘小于0意味着b在a的顺时针方向。既然我们要按顺时针排列，那么a自然排在b前面。

2.3 一个容易绕晕的细节：先半平面，再叉乘

有人可能会问：为什么不能全篇直接用cross(a, b) < 0当比较器，非要额外分半平面？

原因是叉乘只对“角度差在180度以内”的两个向量有效。比如a = (1, -1)，b = (-1, 1)，它们的方向完全相反，叉乘等于0，直接用叉乘根本没法判断谁先谁后。即使把叉乘为0的情况交给距离判断，方向相反的两个点也会被错误地当成同一个方向，排序顺序就会乱掉。

更重要的是，sort要求比较器是一个严格弱序：如果a在b前面，b在c前面，那a必须在c前面。如果不分半平面，会出现a在b前、b在c前、但c又在a前的循环矛盾。sort一旦检测不到合法顺序，直接未定义行为，最常见的表现就是崩溃或者输出乱序。所以半平面划分不是可选项，是必须项。

3. 完整实现与代码逐段解析

3.1 直接能跑的C++代码

下面这份代码用纯整数实现，坐标范围到1e9都没有问题，不需要任何浮点运算。

#include <bits/stdc++.h> using namespace std; struct Point { long long x, y; long long dist2() const { return x * x + y * y; } }; // 叉乘：返回 a->b 的方向关系 long long cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; } // 判断点属于顺时针排序的第几个半圈 // 0 表示从 x 正轴开始顺时针先经过的 180 度范围 // 1 表示剩下的 180 度范围 int half(const Point& p) { if (p.y < 0 || (p.y == 0 && p.x >= 0)) return 0; return 1; } // 从 x 轴正方向开始、顺时针方向的比较器 bool cmpClockwise(const Point& a, const Point& b) { int ha = half(a), hb = half(b); if (ha != hb) return ha < hb; long long c = cross(a, b); if (c != 0) return c < 0; return a.dist2() < b.dist2(); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<Point> p(N); for (int i = 0; i < N; ++i) { cin >> p[i].x >> p[i].y; } sort(p.begin(), p.end(), cmpClockwise); for (const auto& pt : p) { cout << pt.x << ' ' << pt.y << '\n'; } return 0; }

如果激光的中心不是原点而是某个给定点(ox, oy)，读入后做一次平移即可：

for (int i = 0; i < N; ++i) { p[i].x -= ox; p[i].y -= oy; }

之后的排序逻辑不用改，因为所有判断都基于原点。

3.2 每一段代码的设计理由

结构体Point里只存x和y，dist2()用来返回距离平方。之所以用距离平方而不是距离，是因为这里只需要比较大小，开根号完全没必要，反而会增加浮点误差。

cross()函数是全部逻辑的核心，直接返回两个向量的叉乘。注意返回类型用long long，因为坐标如果是1e9量级，叉乘结果可以达到2e18量级，int完全装不下。

half()函数是我认为整道题最值得讲清楚的地方。它把平面切成两个半圈：第一个半圈是y < 0加上x正半轴，覆盖角度从0度顺时针转到180度；第二个半圈是y > 0加上x负半轴，覆盖剩下的180度。这个切分直接决定了排序起点是x轴正方向，很多网上模板用的都是逆时针版的上半平面优先，这里千万不要混。

cmpClockwise()里比较的顺序也很有讲究：先比较half，因为跨半圆叉乘不可靠；然后比较叉乘，决定同半圆内的先后；最后比较距离，解决共线问题。这个顺序缺一不可。

3.3 用一组数据验证排序结果

比如输入：

8 1 0 1 -1 0 -1 -1 -1 -1 0 -1 1 0 1 1 1

程序输出：

1 0 1 -1 0 -1 -1 -1 -1 0 -1 1 0 1 1 1

从(1, 0)出发，走到(1, -1)是第四象限，再到(0, -1)是y负半轴，再到(-1, -1)是第三象限，接着到(-1, 0)是x负半轴，然后进入(-1, 1)第二象限、(0, 1)y正半轴、(1, 1)第一象限。这个顺序正好是从x轴正方向开始顺时针绕一圈，完全符合题目要求。

如果你把点改成都放在同一个方向上，比如(1, 1)、(3, 3)、(2, 2)，代码会按距离从近到远排序，也就是(1,1)、(2,2)、(3,3)。这对应激光先击中近处敌人、再击中远处敌人的逻辑。

3.4 如果起点不是x轴正方向怎么办

有些变体题会把激光初始方向改成任意给定方向，比如指向(0, -1)。处理方式有两种。

第一种是排序后旋转数组。先按x轴正方向排好，然后找到第一个落在起点方向上的点，把数组rotate，让这一段变成开头。注意如果起点方向上有一串同方向的点，它们之间按距离排序，rotate时要整体移动。

第二种是整体旋转坐标系。把起点方向旋转到x轴正方向，所有点坐标跟着旋转，之后再用同一套比较器。这种方法理解起来最直观，但会引入浮点运算，不推荐在N很大的时候用。

我在比赛中最常用的其实是第一种，因为排序逻辑完全复用，只在最后做一次线性扫描和rotate，复杂度仍然是O(N log N)。

4. 那些样例能过、提交却挂的问题

4.1 比较器不是严格弱序，sort会直接乱掉

这是极角排序题最常见的Runtime Error来源。如果你是直接写return cross(a, b) < 0;，那么在两个向量共线反向的时候，叉乘为0，返回false；在另外一些跨半平面的组合中，又可能产生不对称的比较结果，破坏严格弱序要求。

sort本身是一个快排变种，它在比较器失效时会出现非法内存访问，表现就是RE。所以写比较器的时候必须自查三个条件：

• cmp(a, a)必须返回false；
• 如果cmp(a, b)为true，那么cmp(b, a)必须为false；
• 传递性必须成立。

上面代码里的half()正是为了满足传递性而存在的。

4.2 同方向共线点必须按距离排序

题目里的激光是对所有敌人逐个扫射的，同一条射线上靠前的点会挡住靠后的点，所以距离近的必须先被处理。比较器中叉乘为0的情况，本质上是两个点方向相同或相反。方向相同的共线点用距离排序，方向相反的点已经由半平面分组拉开了，不需要担心。

这里有一个很容易被忽略的边界：点正好落在原点时，它的dist2是0，half会被分到前半圈。sort时它可能会被排到整个序列的最前面，这通常是合理的，因为激光从中心射出，如果中心本身有一个敌人，它应该第一个被消灭。如果题意不允许这种情况，读入时单独处理即可。

4.3 为什么我不推荐用atan2排序

用atan2(y, x)能得到一个浮点角度，排序时以角度为key确实很直观。问题是精度。坐标范围一旦大了，两个点角度差可能小于1e-9，浮点比较在极端情况下会把它们判成相等或者顺序颠倒。而且atan2返回值是浮点，sort比较浮点键不如比较整数叉乘可靠。

当然，atan2不是完全不能用。我在调试的时候经常临时打印atan2(p.y, p.x)来看角度是否符合期望，但提交版本一定切回整数叉乘。这个习惯在多次比赛里救过我。

4.4 数据范围溢出和中心点平移问题

叉乘ax * by - ay * bx，如果ax和by都是1e9，那么乘积是1e18，相减后最大到2e18，long long上限约9.22e18，安全。如果题目把坐标范围放到1e18或更大，就必须用__int128。

还有一个常见低级错误：忘记把点相对于中心点平移。如果你把所有点都当成从原点出发处理，而题目给的中心是(ox, oy)，那排序出来完全错误。正确做法是先减掉中心坐标，再做排序；排序完成后如果需要输出原坐标，再加回来。

为了排查这类问题，我习惯在本地跑一个暴力模拟验证：把排序结果拿出来，逐对检查相邻两个点是否满足“下一个点在前一个点的顺时针方向”，也就是cross(v[i], v[i+1]) < 0（最后一个和第一个也检查一次）。如果所有相邻对都满足，排序方向基本不会错。

下面把常见问题整理成一个速查表：

5. 从这道题延伸出去的一些思考

5.1 极角排序在竞赛几何题里的位置

极角排序本身很少作为一道题的最终解法，但它是一堆经典算法的重要预处理。比如凸包的Graham扫描，第一步就是把点按极角排好序；旋转卡壳很多情况下也要基于一个已经有序的极角序列去双指针移动；判断一个点是否在凸多边形内部时，可以用极角二分找到它应该在的扇形区域。

所以Laser Takahashi这道题的价值不在于题目本身有多难，而在于它把“极角排序”这个基础能力单独拎出来考了一次。如果你能把这里的比较器写到一次通过、不靠样例试错，那后面遇到更复杂的几何题会省下大量时间。

5.2 顺手练一练逆时针版本

逆时针版本和顺时针版本是对称的。只需要改两个地方：

• half的划分改为：y > 0以及y = 0且x >= 0为前半圈；
• 同一半圆内，叉乘大于0时返回true，即cross(a, b) > 0。

理解了顺时针版，逆时针版闭着眼也能写出来。我个人的建议是：把这两个比较器封装成两个函数放进模板里，真正比赛时直接调用，不要在考场上临时推叉乘符号。

最后说点我的实际体会

我自己最开始写极角排序也是无脑atan2，直到有一场模拟赛里出现两个夹角小到10的负12次方量级的点，double精度把两个点完全判成了同一个方向，排序结果直接错掉。从那以后我给自己定了一条规矩：能整数就不浮点，能叉乘就不三角函数。

这道Laser Takahashi的所有坑，本质上都在sort的比较器上。只要记住“half分半圈、cross定方向、dist处理共线”这个三步走，极角排序的代码基本能做到一遍过。比赛时如果WA了，不要急着调角度公式，先检查比较器是不是严格弱序，大多时候问题就出在那几个边界条件上。