第十二届蓝桥杯省赛的试题C“直线”，是我印象里非常典型的“看着简单，做起来全是坑”的结果填空题。题目只有一句话：平面上有20×21个整点，横坐标范围是0到19，纵坐标范围是0到20，问这些点一共能确定多少条不同的直线。标准答案是40257，但网上随便一搜就能看到有人算出40247、40258甚至40400的版本。这不是算力问题，而是去重思路出问题。这篇题解想做的事很简单：从读题开始，把暴力枚举、精确去重、数学验证、考场避坑一条线讲透，适合准备蓝桥杯的选手，也适合任何想搞懂几何计数问题的人。
1. 读题三分钟，别把点阵范围和“去重”看漏
1.1 20×21个整点到底分布在哪个范围
先明确点的分布：横坐标x取0、1、2、……、19，一共20个取值；纵坐标y取0、1、2、……、20，一共21个取值。所以总点数是20×21=420个，而不是21×20=420这种乘法顺序的问题——乘法结果一样，但坐标范围不能搞反。如果写程序时把横坐标范围写成0到20、纵坐标范围写成0到19，得到的结果会不同，后面我会再强调这一点。
任意两个不同的点可以确定一条直线，所以如果完全不考虑重复，候选直线数是组合数C(420,2)=87990。这个数字是后续一切讨论的起点。但显然真实答案比87990小得多，因为三点共线、四点共线的情况太多了。比如(0,0)、(1,1)、(2,2)这三个点，任取两个都能确定直线y=x，可它们只能算同一条直线。去重，才是这道题真正想考的。
很多初学者会把“不同直线”错误理解成“不同的斜率”，觉得把斜率种类数出来就完事了。这离正确答案很远。斜率相同不代表直线相同，比如y=x和y=x+1斜率都是1，但它们是两条平行的不同直线。所以标识一条直线必须同时包含方向和位置两部分信息：方向决定它朝哪个方向延伸，位置决定它具体在哪里。
1.2 “不同直线”的判定标准才是计数的核心
如果要用一个键值对表示一条直线，最自然的选择是“斜率+截距”。斜率表示倾斜程度，截距表示在y轴上的位置。只要这两个值完全一样，就是同一条直线；只要其中一个不一样，就是不同的直线。
这个说法本身没问题，问题出在“值”怎么精确表达。比如斜率为2/3的直线，和斜率为4/6的直线，数学上完全一样，因为4/6约分后就是2/3。截距同理。但如果我们直接把两个点代入公式算出一个浮点数，或者用不约分的整数比直接当键，就会把同一条直线拆成多条，把两条平行线又错误合并，答案自然对不上。
所以我建议在读题阶段就建立这样一个框架：计数去重类题目的本质，是给每个对象一个“唯一标识”，标识相同则合并，标识不同则保留。对于直线，最可靠的唯一标识可以是“最简斜率+最简截距”，也可以是后面要讲的“归一化直线方程系数”。前者更直观，后者写代码更省心，两者殊途同归。
2. 浮点数祛魅：为什么斜率和截距不能直接喂进集合
2.1 一个除法就可能让同一条直线“人格分裂”
先说一个最常见的翻车现场：有人用Python写k = (y2 - y1) / (x2 - x1)，把k和小数形式的b直接塞进set。看起来没问题，因为Python的float也是双精度，精度不算低。但浮点数本质上是用二进制近似表示十进制小数，像1/3、2/7这种除不尽或者二进制不循环的小数，都会在某一精度处被截断。
如果只是存一个斜率，同一条直线的不同点对计算出的k可能一样，因为IEEE浮点除法结果相当稳定。真正容易出问题的是截距。截距通常这样算：b = y1 - k * x1。k本身是近似值，再乘一个可能很大的x1，误差就被放大了。同一根直线，你用点A去算b，和用点B去算b，得到的结果在浮点数位上可能差一点点。比如理论上都是2.6666666666666665，实际一个算出2.666666666666666，一个算出2.666666666666667，set一看两个不一样，重复直线就没合并掉。
还有一个更尴尬的情况：斜率非常接近的两条平行线，比如斜率2/3≈0.6666666666666666和斜率2000001/3000000≈0.666667，虽然理论上不同，但如果程序里做过某些近似运算，double比较时有可能被误判相等。这种错误不是每次必现，但一旦出现，你很难定位，因为答案只差个位数。
所以结论很简单：在竞赛中去重，能用整数精确表示就别用浮点数。这一点适用于很多题，包括小数坐标、分数斜率、有理数运算等场景。
2.2 水平线和竖直线：两个容易漏掉的特例
斜率+截距方案里，竖直线是个特例。竖直线方程形如x=c，它的斜率是无穷大，没法用一个有限数表示。常见的处理方式是把斜率存成一个特殊标记，比如字符串'v'，截距存x坐标。
水平线其实不需要特判。水平线斜率是0，完全能用有限斜率表示。但如果你的斜率表示方式是“(dy,dx)的约分分子分母”，水平线的dy是0，dx归一化后是1，同样能正常表示。
很多选手漏掉竖直线，是因为他们在枚举两点时只算了dx = x2 - x1，发现dx等于0就continue跳过了，觉得“竖直线没法求斜率，干脆不要了”。这一跳，20条竖直线全没了。这题答案直接从40257变成了40237左右，丢分丢得非常可惜。
2.3 用分数元组给直线发唯一ID
正确处理方式是自建分数。Python里有fractions.Fraction，竞赛里也能用，但速度略慢、代码略重；自己写gcd约分更轻快，也好理解。
以“斜率+截距”方案为例，核心步骤是：
- 计算
dx = x2 - x1，dy = y2 - y1。 - 如果
dx == 0，说明是竖直线，直接存('v', x1)。 - 否则求出
g = gcd(|dx|, |dy|)，令dx /= g，dy /= g，得到最简方向的整数对。 - 为了保证同一条直线不会因为两点取反变成“另一个斜率”，强制让
dx > 0。如果dx < 0，就把dx和dy同时取反。 - 截距b = (y1 * dx - dy * x1) / dx。为了精确表示，把分子记为
b_num = y1 * dx - dy * x1，分母记为b_den = dx，再求一次gcd约分。 - 最终直线标识为
((dy, dx), (b_num, b_den))，加入集合。
对应Python代码：
from math import gcd from itertools import combinations pts = [(i, j) for i in range(20) for j in range(21)] lines = set() for (x1, y1), (x2, y2) in combinations(pts, 2): dx = x2 - x1 dy = y2 - y1 if dx == 0: lines.add(('v', x1)) continue g = gcd(abs(dx), abs(dy)) dx //= g dy //= g if dx < 0: dx, dy = -dx, -dy b_num = y1 * dx - dy * x1 b_den = dx g2 = gcd(abs(b_num), abs(b_den)) b_num //= g2 b_den //= g2 lines.add(((dy, dx), (b_num, b_den))) print(len(lines)) # 40257运行结果是40257，和官方答案一致。这个方案胜在直观：每个元组都对应唯一一条直线，不会误判，也不会漏判。唯一的问题是代码里关于dx、dy符号和b_num正负的边界条件比较多，写的时候容易乱。所以我更推荐下一个方案：标准式归一化。
3. 标准式归一化：代码最少、坑最少的权威做法
3.1 Ax + By + C = 0的统一化规则
把所有直线写成：
Ax + By + C = 0
其中A、B、C都是整数。水平线、竖直线、斜线全部统一成这个形式，不再需要特殊判断“斜率无穷大”。这是标准式最大的优势。
但同一个方程乘上任意非零常数还是同一条直线。比如x - y = 0和2x - 2y = 0是同一条直线，-x + y = 0也是同一条。所以必须约定一个“标准形态”：
- A、B、C先同时除以它们的最大公约数，让三者互质。
- 符号约定：优先让A为正；如果A等于0，就让B为正。
- 不可能出现A和B同时为0，因为两点不同，总有一个方向上的分量非零。
有了这两条，每条直线只会生成一个唯一的整数三元组(A, B, C)。这个三元组就像直线的身份证号：同一条直线只能有一个号，不同直线必定有不同号。
为什么要让A正、A为零时让B正？因为我们枚举点对的时候，点的顺序是任意的。同样是经过(0,0)和(1,1)的直线，先取(0,0)再取(1,1)算出A=1、B=-1、C=0，反过来取算出A=-1、B=1、C=0。如果没有符号约定，这两组系数会被当成两条直线，答案就翻倍了。
3.2 从两个点推导系数公式
已知两点(x1, y1)和(x2, y2)，怎么快速算A、B、C？最不容易记混的推导是利用向量平行。
直线上任意点(x, y)与点(x1, y1)形成的向量是(x - x1, y - y1)，已知两点形成的方向向量是(x2 - x1, y2 - y1)。两个向量共线，叉积为0：
(x - x1)(y2 - y1) - (y - y1)(x2 - x1) = 0
展开整理：
(y2 - y1)x + (x1 - x2)y + (x2y1 - x1y2) = 0
所以：
A = y2 - y1
B = x1 - x2
C = x2y1 - x1y2
这个公式不需要背，现场推导一遍很快。注意C的符号很容易算反，最好的检查方式是代入(x1, y1)：Ax1 + By1 + C必须等于0。你代入验证一下就知道自己有没有写错。
3.3 Python实现与答案打印
标准式写出的Python代码非常短：
from itertools import combinations from math import gcd pts = [(i, j) for i in range(20) for j in range(21)] lines = set() for (x1, y1), (x2, y2) in combinations(pts, 2): A = y2 - y1 B = x1 - x2 C = x2 * y1 - x1 * y2 g = gcd(gcd(abs(A), abs(B)), abs(C)) A //= g B //= g C //= g if A < 0 or (A == 0 and B < 0): A, B, C = -A, -B, -C lines.add((A, B, C)) print(len(lines)) # 40257这里有几个实现细节值得说明。
第一，gcd(gcd(abs(A), abs(B)), abs(C))的写法保证了三个数的最大公约数都能被除掉。注意gcd的顺序不能省，如果写成gcd(abs(A), abs(B), abs(C))在Python3.9以上也支持，但为了兼容性还是嵌套写更稳。
第二，当A=B=0时，两点重合，但组合枚举保证两点不同，所以不会出现。理论上有数学洁癖的话可以加一行if A == 0 and B == 0: continue，不影响结果。
第三，符号判断只用了A < 0 or (A == 0 and B < 0)。如果A为负，取反后A为正，B、C符号同时变化。如果A恰好为0，那么看B，B为负就取反。这样所有直线都被统一到“A尽量正”的标准形态。
最终输出40257。这个方案不需要单独管水平线和竖直线，因为水平线会生成A=0、B=某个非零数、C=某个数；竖直线会生成A=某个非零数、B=0、C=某个数。一切交给归一化和set去重，逻辑非常干净。
4. 换个角度验证：按方向向量分组也能算出40257
4.1 方向向量与原始斜率的关系
暴力枚举完拿到40257之后，我习惯再用一个完全不同思路验证一遍，防止代码里出现系统性bug。这里分享一个“按方向分组”的数学做法。
考虑一条斜线，它的方向可以写成最简整数对(a, b)：x方向走a步，y方向走b步。为了避免方向重叠，要求a和b都为正整数，且gcd(a, b) = 1。所有正斜率直线都能对应一个(a, b)，比如斜率2对应(a, b)=(1,2)，斜率2/3对应(a, b)=(3,2)。由于点阵宽度最大跨度是19，高度最大跨度是20，所以a的范围是1到19，b的范围是1到20。
同一个方向(a, b)的所有直线是彼此平行的，它们之间的区别在于“位置”。这个位置怎么精确表示？可以取直线上任意一点(x, y)，计算特征值：
c = ay - bx
为什么取这个式子？因为如果把x变成x+a，y变成y+b，那么：
a*(y+b) - b*(x+a) = ay + ab - bx - ab = ay - bx
恰好不变。也就是说，沿着这条直线方向移动时，c保持不变；而把直线往垂直方向平移一个小距离，c会改变。所以同一个方向(a,b)下，每个c值对应一条不同的平行直线。
4.2 截距分组公式与“单点直线”陷阱
按照上面的思路，有人会直接写：对每个方向(a,b)，统计集合{ay - bx | 点(x,y)属于点阵}的大小，累加起来就是斜线数量。
这里有个不容易察觉的陷阱：并不是每一个c都能对应一条“由点阵中至少两个点确定”的直线。
比如方向(1,1)代表斜率1。计算c = y - x，点(0,0)得到c=0，点(19,20)得到c=1，这些都好理解。但点(19,0)得到c = 0 - 19 = -19，这条c=-19的直线y = x - 19在点阵里只经过了(19,0)这一个点。它确实存在，但它不能用题目中“任意两点确定一条直线”的方式产生，因为点阵里找不到第二个点在这条直线上。所以计数时要滤掉这些“只过一个点”的c。
正确做法是：对每个方向(a,b)，把所有点按c值分组，数出每个组里有多少个点，只有点数大于等于2的组，才算一条直线。
对应Python验证代码：
from math import gcd base = 21 + 20 # 水平线21条，竖直线20条 ans = base for a in range(1, 20): for b in range(1, 21): if gcd(a, b) != 1: continue cnt = {} for x in range(20): for y in range(21): c = a * y - b * x cnt[c] = cnt.get(c, 0) + 1 # 正斜率和负斜率对称，所以乘2 ans += 2 * sum(1 for v in cnt.values() if v >= 2) print(ans) # 40257这段代码的逻辑和标准式枚举完全等价，但视角不同，非常适合互相印证。水平线单独算21条，竖直线单独算20条，剩下的正负斜线按方向分组。注意负斜率方向会和正斜率方向数量对称，所以直接乘2。
4.3 方向(1,1)手算示范与汇总结果
拿方向(1,1)手算验证一下：点阵中x范围0到19，y范围0到20，c=y-x的取值范围是从-19到20，一共40个整数。但是c=-19只对应点(19,0)，c=20只对应点(0,20)，这两个组只有一个点，不能算。所以方向(1,1)的正斜率直线是38条，负斜率对称也是38条，加起来76条。你看，如果直接用40个c值相加，就会多算两条线。
其他方向的统计逻辑相同，只是a和b不再相等，c的取值范围更宽，单点组也更多。跑完整个双层循环后，最终累加得到40257，和标准式枚举结果一致。
组合数学方法的价值不只是“多一个答案对照”，它还能让你理解直线计数的本质：先锁定方向，再区分位置。对应到标准式解法里，方向就是(A,B)的比例关系，位置就是C与(A,B)的比例关系，归一化则是把所有相同比例合并成同一个整数三元组。
5. 考场之外的思考：这道题的踩坑点全回顾
5.1 枚举点对时最容易写错的坐标边界
这题很多选手写for i in range(20)和for j in range(21)，看着没问题，但有人会把横坐标写成range(21)，纵坐标写成range(20)，假设自己很聪明地交换了顺序。实际上题目明确要求横坐标0到19、纵坐标0到20，交换之后点阵形状变成21×20，答案会跟着变。
怎么防这个问题？一个很土但有效的办法：先输出len(pts)，确认点数是420，再输出min(x), max(x), min(y), max(y)，看范围和题目是否一致。这种校验在小规模题里花不了几毫秒，但能避免灾难性的全盘错误。
另外，枚举所有点对时要保证不重复。用combinations(pts, 2)或者双重循环for i in range(n): for j in range(i+1, n):都行。最怕的是里层循环写成for j in range(n)，每对点会被计算两遍，虽然最终结果可能不会翻倍，因为有去重逻辑兜底，但时间浪费是次要的，主要问题是如果符号约定写得不够好，同一条直线可能以两种顺序生成两个不同标识，导致结果错误。
5.2 gcd化简和符号约定：统一比技巧更重要
标准式解法最关键的细节就是化简和符号。有人觉得g = gcd(abs(A), abs(B), abs(C))写起来麻烦，简化成只对A和B求gcd，结果C没有约分，导致同一条直线出现多个不同元组，答案虚高。
这里有个小技巧：求完gcd后，如果C是0，gcd(..., 0)不会出问题，Python里gcd(x, 0)返回x。只有当A和B同时为0，gcd(0, 0)才会返回0，而题目里的两点不同，A和B不会同时为0，所以可以放心。
符号约定同样重要。如果忘了统一的符号规则，直线x - y = 0和-x + y = 0会被set当成两条不同的线。我见过有人为了避免这个问题，把所有直线都固定成C大于0，再不行就让第一个非零系数为正。这种做法可行，但不如“A正，A为零时B正”来得自然。记住一点：去重代码不怕笨，怕不一致。你用哪套约定都可以，但必须保证同一个集合里只会出现同一套写法。
5.3 如果点阵规模变大，暴力还够用吗
420个点，C(420,2)=87990次枚举，每次做几次gcd，Python跑起来几乎瞬间完成。所以这道题暴力完全够用。
但如果题目点阵变成2000×2000，枚举量就是C(4,000,000,2)，直接不可行。这时候需要更数学的做法：比如按方向向量扫描，或者用欧拉函数统计互质方向，再结合直线在边界上的截距分布来计算。真题里大概率不会考到那么大规模，但理解这个递进关系有助于你判断“什么时候可以无脑暴力，什么时候必须优化”。
从另一个角度看，这道题也提示我们：结果填空题的答案虽然可以直接填数字，但过程里藏着的原理对后面的大题同样有用。比如线性方程去重、分数精确运算、gcd归一化，这些技巧在几何、数论、组合题里反复出现。把这道题的每个坑都踩明白，比单纯记一个40257有价值得多。
最后分享一点我个人经验：做完这道题后，我写任何几何计数类题，都会先问自己三个问题——“对象怎么唯一标识”“浮点数能不能换成整数”“特例有没有被包含”。这三点不搞清楚，代码写得再华丽也会在边界处翻车。希望你也能从这道“直线”里带走这些比答案更持久的东西。
