企业官网建设流程全解析

开头（≥200字）：

每年的秋招季都会有一批“看着像小公司、实际上技术题难出天际”的存在，酷家乐绝对算其中一个。作为一家做云设计平台的公司，它2020校招的几何算法A卷在圈子里流传度相当高，不是因为题目有多偏多怪，而是它把“家装设计”这个场景里的几何问题浓缩成了一份非常典型的算法考卷。凡是投过图形学、CAD、BIM、渲染相关岗位的同学，多半都听过这份卷子的名号。

这份卷子考察的东西并不玄乎，核心就是二维平面几何和三维空间的表达、计算、判交与变换。但它牛就牛在，每道题背后都对应着酷家乐实际业务里真实发生过的场景：户型图的墙体识别、橱柜拉手在转角处的碰撞、吊顶与灯槽的路径计算、水电管道在墙体里的走向排布。换句话说，这不是一份纯刷LeetCode能搞定的卷子，它要求你既会推公式，又能把公式落到工程代码里。

这篇文章我会把这份“几何算法A卷”的考察方向、背后的业务逻辑、每一类题型的解题思路以及实际考场上的踩坑经验全部拆开讲一遍。文章面向两类人：一是准备投酷家乐或其他云设计、CAD、渲染方向岗位的应届生，二是对计算几何感兴趣、想知道这些算法在真实产品里怎么落地的开发者。看完你会明白，这份卷子考的其实不只是几何，而是你能否用数学解决工程问题的综合能力。

1. 为什么一家云设计平台会拿几何算法当校招考题

想搞明白这份卷子，得先搞明白酷家乐是家什么公司。它做的是“云设计平台”，也就是让用户在浏览器里完成户型绘制、室内设计、效果图渲染和施工图输出。这个产品形态决定了它的技术栈里，几何计算不是某一个模块的事情，而是渗透到了产品的每一个角落。

1.1 云设计场景里的几何问题无处不在

我这里随便列几个酷家乐产品里真实存在的功能，你感受一下：

• 用户画户型图的时候，墙体是一个一个矩形拼出来的，但两堵墙相交之后，墙角处会出现一条45度的斜切缝，系统要把这个缝自动补平。这是典型的“多边形并集/布尔运算”问题。
• 设计师把一个柜子拖进房间里，系统要自动判断柜子有没有穿模、是不是贴着墙、离门有没有留出开启空间。这是“碰撞检测”和“最小距离计算”。
• 渲染效果图的时候，阳光透过窗户照进来，光斑要落在木地板上，并随着太阳角度变化而移动。这是“射线与平面求交”的实时计算。
• 水电布线的时候，管道要从配电箱走到各个插座，走线路径要避开梁柱、沿着墙根走。这是“最短路径+障碍物规避”的组合问题。

这些功能有一个共同点：它们都发生在“三维空间里、但最终呈现在二维屏幕和几何数据上”的交叉地带。而校招笔试不可能让你现场做一整套产品功能出来，所以出题人把里面最核心的数学内核抽出来，变成了试卷上那七八道纯几何题。你把这些题做对了，基本上就证明你具备了处理上述真实场景的数学功底和编码能力。

1.2 酷家乐对几何算法岗位的真实能力画像

从这份A卷的题型结构来看，酷家乐对校招候选人的能力预期是很具体的。它不指望你是一个成熟的图形学大佬，但希望你具备三样东西：

第一，扎实的高中/大学几何基础。向量运算、点线关系、多边形性质这些不能打磕巴。第二，把几何问题“程序化”的能力。给你一个几何描述，你得能想到用哪种数据结构去表达、用哪个公式去计算、边界条件是什么。第三，空间想象力。题目会给你一个三维场景的文字描述，你需要在脑子里把它转成坐标系和方程，再转成代码逻辑。

这三样东西对应到试卷上，就是不同分值的题目梯度。基础题考向量和点线关系，中等题考多边形和面积计算，难题考三维变换和射线求交。整张卷子下来，不会出现“偏题怪题”，但它会把简单问题藏在复杂的场景描述里，考察你是不是真的理解了本质，而不是只会套公式。

2. 拆解几何算法笔试的核心考察范围

我根据当年流出来的题目回忆版和多个参与过笔试的同学反馈，把这份A卷的考察范围大致归成了六个方向。这六个方向不仅适用于酷家乐，也适用于几乎所有云设计、CAD、游戏引擎方向的算法岗笔试。

2.1 二维基础：向量与点线关系的判断

这一块是整张卷子的地基。向量加减、点积叉积、两点间距离、点到直线的距离、判断点在直线哪一侧……这些知识本身不复杂，但出题人会换着花样把它们组合起来。

举个例子，试卷里有一道很经典的题：给定一个点P和一个由A、B两点构成的线段，判断P在线段的左侧、右侧还是线上。很多人第一反应是“用斜率比较”，但这在工程上是错误的做法，因为斜率在垂直线段上会变成无穷大，直接除以零崩溃。正确的做法是用叉积符号来判断：

AB = B - A AP = P - A cross = AB.x * AP.y - AB.y * AP.x

如果cross大于0，P在AB左侧；小于0则在右侧；等于0说明共线。但共线之后还要再判断P是否真的落在线段范围内，而不是在延长线上，这就需要再加一步“点的包围盒判断”。这题看起来简单，但能把“叉积判向+包围盒判段”写完整、边界条件处理干净的人，其实不到一半。

另一个高频基础题是“判断两个线段是否相交”。标准做法是“跨立实验”：对线段AB和CD，先判断A、B是否在CD两侧，再判断C、D是否在AB两侧。但这里有个非常隐蔽的坑：当两条线段共线时，跨立实验会失效，需要额外处理。很多人在这一步没注意，导致特殊情况下判错。我见过大量候选人在这种“简单题”上扣分，非常可惜。

2.2 多边形操作：面积、凸包与点在多边形内

多边形相关的题目在A卷里占了相当大的比重，因为它与户型图编辑、区域划分的业务强相关。

面积计算是最基本的。给定一个顶点按顺序排列的多边形，求它的面积。标准做法是用“鞋带公式”（也叫叉积坐标公式）：

area = 0 for i in range(n): j = (i + 1) % n area += polygon[i].x * polygon[j].y area -= polygon[j].x * polygon[i].y area = abs(area) / 2

这个公式的原理是“把多边形分割成若干个三角形，然后求有向面积之和的一半”。理解这个原理比背公式重要，因为它顺便解释了另一个问题：为什么顶点是顺时针还是逆时针，会影响area的正负号，但取绝对值后结果一样。

凸包的考察方式通常是“给定一堆点，求包含所有点的最小凸多边形”。经典解法有Graham扫描法和Andrew单调链法。坦白说，这道题是整张卷子里最“计算机科学”的题，因为它不仅考几何，还考排序和栈的应用。Andrew算法的手写模板我建议每个候选人都提前备好，毕竟考场上现推容易出bug。

“判断点是否在多边形内”也是常客。射线法是最常用的：从点P向右发一条水平射线，统计它与多边形边的交点数，奇数是内部，偶数是外部。但工程里的坑在于：当射线恰好经过多边形的顶点时，需要特殊处理“顶点重叠计数”的问题。我的处理技巧是“约定射线穿过顶点时，只统计边的一侧（比如只统计y坐标递增方向经过该顶点的边）”，这样能稳定避免歧义。

2.3 三维扩展：空间几何体与变换

如果说二维题是热身，那三维题目就是分水岭了。酷家乐毕竟是云设计平台，三维空间的处理能力是核心中的核心。

三维向量的叉积、点积、混合积是基础，但更关键的是三维图形的表达和变换。试卷里常见的题型包括：给定三维空间中的一个三角形和一个点，判断点是否在三角形上；给定一条射线与一个平面，求交点坐标；给定一个模型变换矩阵（旋转+平移），求一个点在变换后的新坐标。

这里我必须强调一个点：很多人在准备这类题时，把精力放在了“记忆旋转矩阵”上，但酷家乐真正想考察的是“你理不理解变换的内在逻辑”。因为在实际产品里，设计师拖拽模型时，系统需要把屏幕上的鼠标移动量转换成三维空间里的模型旋转量，这背后是“视锥体坐标转换”和“矩阵链式乘法”的组合。如果只背公式而不理解，换一个场景就抓瞎了。

三维部分最常见的扣分点是“坐标系习惯不一致”。比如旋转矩阵在左手坐标系的定义和右手坐标系会差一个负号，如果你做题前没有留意题目用的是哪种坐标系，很可能方向就反了。我的建议是：拿到题目先判断坐标系类型，再动笔。哪怕题目没说，也要在答题时注明“假设使用右手坐标系”。

2.4 几何工具库的合理使用

笔试题目通常会注明“禁止调用现成几何库”或者“允许使用标准库但必须实现核心逻辑”。实际上，在LeetCode一类的平台上，计算几何题目自带的STL支持很有限，你几乎总是需要自己手写Point和Vector类。

我个人的习惯是在笔试开始前，先在草稿纸上写好一个最小可用的几何工具模板：

class Point: def __init__(self, x=0, y=0): self.x = x self.y = y def cross(a, b, c): return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) def dot(a, b, c): return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y)

先说结论：这个模板在真实笔试里价值不大。为什么？因为笔试的题通常都是“多步计算”而非“单点函数调用”。比如“判断一个四边形是否为矩形”这道题，考察的是对角线相等且互相平分的性质，不是让你调一个isRectangle()函数。你会手写Point类和cross函数只是及格线，真正拉开差距的是你能否快速把这些工具组合起来解决一道完整的问题。

但另一个角度看，提前准备好模板能帮你节省“边写边回忆语法”的时间，让你更快进入状态，这在实际限时笔试里也是一种优势。

3. 实战向的解题思路与代码模板

接下来我把A卷里出现概率最高、最值得提前准备的几类题目展开讲，每一类都给出解题思路和可直接套用的代码。

3.1 判断两条线段是否相交（含共线处理）

先说结论。两条线段AB和CD相交，分两种情况：规范相交（交点在线段内部）和非规范相交（交点是端点或者共线重叠）。

规范相交的判断用跨立实验：

• 叉积(cross(A,B,C) * cross(A,B,D)) < 0，说明C和D分别在AB的两侧
• 叉积(cross(C,D,A) * cross(C,D,B)) < 0，说明A和B分别在CD的两侧

如果两个条件同时满足，必然相交。但工程上更稳妥的做法是判断“<= 0”，这样把“端点恰好落在另一条线段上”的情况也算进去了。

共线重叠的判断方式：先用叉积判断四点是否共线（cross(A,B,C) == 0且cross(A,B,D) == 0），然后判断投影区间是否重叠。这里有个小技巧：不需要同时判断x轴和y轴投影，只需要判断x轴投影（如果线段不垂直于x轴）或者y轴投影（如果线段垂直于x轴）就可以了。稳妥起见就两个轴都判断。

我写一个完整的Python实现：

class Point: def __init__(self, x, y): self.x = x self.y = y def cross(p1, p2, p3): return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) def on_segment(p1, p2, p3): return (min(p1.x, p2.x) <= p3.x <= max(p1.x, p2.x) and min(p1.y, p2.y) <= p3.y <= max(p1.y, p2.y)) def segments_intersect(p1, p2, p3, p4): d1 = cross(p3, p4, p1) d2 = cross(p3, p4, p2) d3 = cross(p1, p2, p3) d4 = cross(p1, p2, p4) if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and \ ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)): return True if d1 == 0 and on_segment(p3, p4, p1): return True if d2 == 0 and on_segment(p3, p4, p2): return True if d3 == 0 and on_segment(p1, p2, p3): return True if d4 == 0 and on_segment(p1, p2, p4): return True return False

这个代码的好处是覆盖了规范相交和所有非规范相交情况。注意最后的四个if判断，顺序无所谓，但不能少。少了任何一个都会漏判“端点在另一条线段上”的情况。

踩坑提醒：不要为了图快写成“只判断跨立实验就返回”的版本，那个版本碰到共线是必挂的。也别用斜率比较法，除以零的问题会让你后期debug到怀疑人生。

3.2 计算多边形面积与判断顶点顺序

多边形的面积计算听着简单，但实际代码里有一个非常常见的错误：忘记处理“自相交多边形”。

什么是自相交多边形？就是顶点顺序绕圈时，边与边之间发生了交叉。比如五角星，它的顶点如果按顶点索引正序连接，会得到一个五角星形状的自相交多边形。这种情况下鞋带公式算出来的是一个“有向代数面积”的累积，而不是直观的图形面积。

如果题目没有特别说明“输入多边形保证是简单多边形”，你可以默认它一定是简单多边形，因为出题人不会在这个地方故意坑你。但你自己心里要清楚：鞋带公式适用于简单多边形。如果题目明确说明“多边形可能自交”，那就得先把多边形三角剖分，再分别求每个三角形的面积，这个复杂度会高很多，一般笔试不会出。

顶点顺序的判断也很简单：用鞋带公式算出来的“带符号面积”，如果为正就是逆时针，为负就是顺时针。这个结论在二维几何里非常常用，比如实现多边形填充算法时，需要保证顶点是逆时针顺序，否则渲染管线会做背面剔除导致显示异常。

一个常被忽略的细节：浮点数精度。鞋带公式累加的数值可能很大，特别是多边形顶点坐标值达到百万级别时，float会丢精度。建议用double，并且最终取绝对值时再处理。这行字看着不起眼，但在真实笔试里真的有人因为用float丢精度而挂掉。

3.3 点在多边形内的射线法实现

射线法的完整实现看起来简单，但有几个边界条件需要仔细处理。我先把代码放出来：

def is_point_in_polygon(pt, poly): n = len(poly) inside = False for i in range(n): p1 = poly[i] p2 = poly[(i + 1) % n] if (p1.y > pt.y) != (p2.y > pt.y): x_intersect = (p2.x - p1.x) * (pt.y - p1.y) / (p2.y - p1.y) + p1.x if pt.x < x_intersect: inside = not inside return inside

这里用的是经典的水平射线法。核心逻辑是：如果点P的y坐标恰好落在一条边的两个端点的y坐标之间（注意是严格一侧上、一侧下），就计算这条边在P所在高度上的x坐标，判断射线是否穿过。

边界条件处理：

• 当P的y坐标恰好等于某个顶点的y坐标时，会出现“射线穿过顶点”的情况。这个实现里用(p1.y > pt.y) != (p2.y > pt.y)来规避：如果两个端点都在同一侧，或者恰好有一个端点等于P的y坐标，条件都不会满足，从而避免重复计数。
• 当P落在多边形边上时，这个函数会返回True或False，结果不确定。如果题目要求“把边上的点也算作内部”，需要额外加一步判断。

这段代码是“能跑且大概率正确”的版本。但在竞赛与笔试中，还有更快的方案——基于“扫描线”的做法，但那需要先做预处理排序，对笔试短时间内完成来说性价比不高。除非你提前准备了模板，否则还是用射线法稳妥。

3.4 三维射线与平面求交

三维部分的高频题：给定一个平面（用法向量n和平面上一点P0表示）和一条射线（起点O、方向向量d），求射线与平面的交点。

解题步骤如下：

1. 计算denom = dot(n, d)。
2. 如果|denom|小于某个极小值（比如1e-9），说明射线与平面平行或共面，没有唯一交点。
3. 计算t = dot(n, P0 - O) / denom。
4. 如果t < 0，说明交点在射线的反方向，实际上射线没有打到平面。
5. 否则交点坐标就是O + t * d。

代码实现：

def ray_plane_intersect(ray_origin, ray_dir, plane_point, plane_normal): denom = dot(plane_normal, ray_dir) if abs(denom) < 1e-9: return None t = dot(plane_normal, plane_point - ray_origin) / denom if t < 0: return None return ray_origin + ray_dir * t

这个题最容易被忽略的点是符号问题。P0 - O的方向写反，会导致t的符号反了，交点到射线的反方向去了。这种bug不看实际运行结果根本发现不了。

实际笔试中，这个考点通常会和“射线与三角形求交”结合在一起。如果你已经解出了射线与平面交点，那么下一步就是判断这个点是否在三角形内部。判断方法可以用“重心坐标法”，也可以用“同向法”——分别判断点是否在三角形三条边的同一侧。两个方法都可以，但重心坐标法对浮点误差的容忍度更高，也更规范。

3.5 复合题型：矩形重叠与最近点对

A卷里还有一类“看似简单，实则全考细节”的题。典型代表是“判断两个矩形是否重叠”和“求一组点中距离最近的两个点”。

矩形重叠判断最简单的方法是反证法：两个矩形不重叠，意味着其中一个在另一个的左边、右边、上边或下边。写成代码：

def is_rect_overlap(r1, r2): return not (r1.x2 < r2.x1 or r2.x2 < r1.x1 or r1.y2 < r2.y1 or r2.y2 < r1.y1)

这个解法比“枚举所有顶点是否在另一个矩形内”高效得多，也更准确地处理了“边重合但面积为零”的边界情况。

最近点对问题则有明显的水平区分。暴力法两两求距离是O(n^2)，n为几千的时候勉强能跑，但笔试的数据量如果到十万级别，就必须用分治法。分治法的核心是：

1. 把点集按x坐标排序。
2. 递归分治，求左半和右半内部的最近点对距离d。
3. 只在“距离中线距离小于d”的带状区域里，检查跨左右两边的点对。

这个分治法在笔试时间紧张时不容易徒手写对。我的建议是：如果目标岗位是几何算法方向，提前背熟分治模板。如果你只是其他方向的候选人，看到这道题应该评估时间成本，实在不行就写暴力法，拿部分分数也比空着强。

4. 阅卷视角：这些细节决定了你能否进面试

笔试不是只考“做对没有”，还考“做得像不像一个合格的工业级开发者”。我从参加过这类卷子批改的面试官朋友那里听到过一些反馈，这里分享给你。

4.1 命名规范与代码可读性

整洁的变量命名会影响面试官对你的第一印象。如果你的代码里全是p1、p2、p3、p4这样的命名，面试官会认为你平时写代码时不太考虑可维护性。

命名建议：

• 用point_a, point_b而不是p1, p2。
• 用cross_value、dot_value而不是d1, d2。
• 用is_intersect而不是check()。

本质上，面试官在阅卷时会试图判断“这个候选人的代码能不能进生产环境”。虽然笔试代码不是生产代码，但代码风格会暴露你平时的习惯。即使题目做对了，一个整洁的命名风格绝对能加分。

4.2 边界条件的完备性

我给候选人的建议是，每写完一道题，自己立刻检查三类边界条件：

• 空输入：多边形没有顶点、点集为空。
• 重复输入：多个点坐标相同。
• 退化情况：三点共线、线段长度为0、法向量为零向量。

这三点如果在代码里都考虑到了，即使最终答案有细微bug，面试官也会认为你具备工程严谨性。反之，如果主逻辑写出来了但边界条件一塌糊涂，面试官会认为“这人在生产环境里会写出低级的崩溃事故”。

4.3 时间复杂度与空间复杂度的权衡说明

试卷上的每道题都标了数据范围，你需要在答题时根据数据范围选择合适的算法。比如“判断点是否在多边形内”如果多边形顶点数不超过100，O(n)的射线法就够了。但如果多边形顶点数达到10^6，你需要用扫描线预处理成O(log n)查询，这就是不同的解法了。

面试官期待看到的是候选人能够自己判断复杂度，并在答案中注明“这个解法是O(n log n)，因为需要先排序”。不要在O(n^2)的暴力法代码旁边什么都不写，面试官会默认你不知道还有更优解。哪怕你写的是最优解，也建议在注释里用一行说明时间复杂度，这样能更直观地展示计算思维能力。

5. 常见扣分点与备赛建议速查

根据往年笔试的反馈，我整理了一个高频扣分点对照表，你可以对照着自查。

5.1 高频扣分点列表

5.2 备赛建议：三条实际可执行的路径

先说基础路线。如果你的时间只有两周，我建议你把重心放在以下内容上：向量与点线关系（包括叉积点积的所有性质）、线段相交判断、多边形面积与凸包、点在多边形内判断。这些是A卷的“必考送分题”。你不需要背太多模板，但需要能在30分钟内手写完成并保证无bug。

再说进击路线。如果你的时间有四周，可以在基础之上加入：三维向量与空间平面、射线与三角形求交、坐标变换与矩阵乘法、矩形重叠与最近点对。这些都是中高难度题目，能做出这类题基本意味着你已经超过80%的候选人了。

最后是模拟路线。无论准备多久，考前一定要做至少三次完整的定时模拟。找一份类似的几何算法题集，设定90分钟倒计时，完全模拟笔试环境。你会发现“平时的自己能想出来的思路”和“考场上的自己能在有限时间内写出来的代码”差距极大。模拟的价值就是让你提前适应这种差距，调整做题节奏。

6. 写在最后：一些关于几何算法的碎碎念

我从第一次接触计算几何到现在，前前后后背过、手写过、踩坑过不少这类题目。如果你问我这份酷家乐A卷到底难不难，我会说：它比纯算法题要“接地气”得多，因为它考的东西基本都能在真实产品里找到对应的功能模块。但同时，这也意味着它容不得你“背模板糊弄过去”。

我个人的体会是，几何算法的备考和别的算法方向不太一样。普通的算法题考的是“数据结构+逻辑”，而几何算法题更考“数学直觉+空间想象力+精度意识”三者的结合。很多人刷了几百道LeetCode再去考几何卷，反而被一道“判断点在三角形内部”的题打懵了，原因就是他们从来没有真正理解过叉积这个工具在几何里的核心地位。

如果你打算投相关岗位，我会建议你花一个下午的时间，完整推导一遍“叉积为什么可以用来判断点与直线的左右关系”，弄懂“鞋带公式为什么能算面积”，搞清楚“射线法遇到顶点时为什么要做特殊处理”。这三个问题想明白了，至少能覆盖这份考卷60%以上的考点。剩下的，就是多练习、多踩坑、多复盘。

最后分享一个小技巧：考场时间不够的时候，“拿能拿的分”比“挑战难题”更重要。A卷的题目通常会从易到难排列，但偶尔也有“开头即难题”的变态情况。建议拿到卷子后先花两分钟扫一遍全部题目，然后从“思路最清晰、代码最熟练”的题开始写，而不是盲目地按顺序做题。这个策略帮我在多次笔试里稳稳保住及格线，也推荐给你。

祝顺利。