★ FEATURED ARTICLE 第十二届蓝桥杯省赛的试题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×21420个而不是21×20420这种乘法顺序的问题——乘法结果一样但坐标范围不能搞反。如果写程序时把横坐标范围写成0到20、纵坐标范围写成0到19得到的结果会不同后面我会再强调这一点。任意两个不同的点可以确定一条直线所以如果完全不考虑重复候选直线数是组合数C(420,2)87990。这个数字是后续一切讨论的起点。但显然真实答案比87990小得多因为三点共线、四点共线的情况太多了。比如(0,0)、(1,1)、(2,2)这三个点任取两个都能确定直线yx可它们只能算同一条直线。去重才是这道题真正想考的。很多初学者会把“不同直线”错误理解成“不同的斜率”觉得把斜率种类数出来就完事了。这离正确答案很远。斜率相同不代表直线相同比如yx和yx1斜率都是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.666666666666667set一看两个不一样重复直线就没合并掉。还有一个更尴尬的情况斜率非常接近的两条平行线比如斜率2/3≈0.6666666666666666和斜率2000001/3000000≈0.666667虽然理论上不同但如果程序里做过某些近似运算double比较时有可能被误判相等。这种错误不是每次必现但一旦出现你很难定位因为答案只差个位数。所以结论很简单在竞赛中去重能用整数精确表示就别用浮点数。这一点适用于很多题包括小数坐标、分数斜率、有理数运算等场景。2.2 水平线和竖直线两个容易漏掉的特例斜率截距方案里竖直线是个特例。竖直线方程形如xc它的斜率是无穷大没法用一个有限数表示。常见的处理方式是把斜率存成一个特殊标记比如字符串v截距存x坐标。水平线其实不需要特判。水平线斜率是0完全能用有限斜率表示。但如果你的斜率表示方式是“(dy,dx)的约分分子分母”水平线的dy是0dx归一化后是1同样能正常表示。很多选手漏掉竖直线是因为他们在枚举两点时只算了dx x2 - x1发现dx等于0就continue跳过了觉得“竖直线没法求斜率干脆不要了”。这一跳20条竖直线全没了。这题答案直接从40257变成了40237左右丢分丢得非常可惜。2.3 用分数元组给直线发唯一ID正确处理方式是自建分数。Python里有fractions.Fraction竞赛里也能用但速度略慢、代码略重自己写gcd约分更轻快也好理解。以“斜率截距”方案为例核心步骤是计算dx x2 - x1dy y2 - y1。如果dx 0说明是竖直线直接存(v, x1)。否则求出g gcd(|dx|, |dy|)令dx / gdy / 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)算出A1、B-1、C0反过来取算出A-1、B1、C0。如果没有符号约定这两组系数会被当成两条直线答案就翻倍了。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 - y1B x1 - x2C 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以上也支持但为了兼容性还是嵌套写更稳。第二当AB0时两点重合但组合枚举保证两点不同所以不会出现。理论上有数学洁癖的话可以加一行if A 0 and B 0: continue不影响结果。第三符号判断只用了A 0 or (A 0 and B 0)。如果A为负取反后A为正B、C符号同时变化。如果A恰好为0那么看BB为负就取反。这样所有直线都被统一到“A尽量正”的标准形态。最终输出40257。这个方案不需要单独管水平线和竖直线因为水平线会生成A0、B某个非零数、C某个数竖直线会生成A某个非零数、B0、C某个数。一切交给归一化和set去重逻辑非常干净。4. 换个角度验证按方向向量分组也能算出402574.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到19b的范围是1到20。同一个方向(a, b)的所有直线是彼此平行的它们之间的区别在于“位置”。这个位置怎么精确表示可以取直线上任意一点(x, y)计算特征值c ay - bx为什么取这个式子因为如果把x变成xay变成yb那么a*(yb) - b*(xa) 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)得到c0点(19,20)得到c1这些都好理解。但点(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到19y范围0到20cy-x的取值范围是从-19到20一共40个整数。但是c-19只对应点(19,0)c20只对应点(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(i1, n):都行。最怕的是里层循环写成for j in range(n)每对点会被计算两遍虽然最终结果可能不会翻倍因为有去重逻辑兜底但时间浪费是次要的主要问题是如果符号约定写得不够好同一条直线可能以两种顺序生成两个不同标识导致结果错误。5.2 gcd化简和符号约定统一比技巧更重要标准式解法最关键的细节就是化简和符号。有人觉得g gcd(abs(A), abs(B), abs(C))写起来麻烦简化成只对A和B求gcd结果C没有约分导致同一条直线出现多个不同元组答案虚高。这里有个小技巧求完gcd后如果C是0gcd(..., 0)不会出问题Python里gcd(x, 0)返回x。只有当A和B同时为0gcd(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次枚举每次做几次gcdPython跑起来几乎瞬间完成。所以这道题暴力完全够用。但如果题目点阵变成2000×2000枚举量就是C(4,000,000,2)直接不可行。这时候需要更数学的做法比如按方向向量扫描或者用欧拉函数统计互质方向再结合直线在边界上的截距分布来计算。真题里大概率不会考到那么大规模但理解这个递进关系有助于你判断“什么时候可以无脑暴力什么时候必须优化”。从另一个角度看这道题也提示我们结果填空题的答案虽然可以直接填数字但过程里藏着的原理对后面的大题同样有用。比如线性方程去重、分数精确运算、gcd归一化这些技巧在几何、数论、组合题里反复出现。把这道题的每个坑都踩明白比单纯记一个40257有价值得多。最后分享一点我个人经验做完这道题后我写任何几何计数类题都会先问自己三个问题——“对象怎么唯一标识”“浮点数能不能换成整数”“特例有没有被包含”。这三点不搞清楚代码写得再华丽也会在边界处翻车。希望你也能从这道“直线”里带走这些比答案更持久的东西。
阅读完成 · 觉得有帮助？
